DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2017.28

Induced Embeddings into Hamming Graphs

Authors: Martin Milanic, Peter Mursic, and Marcelo Mydlarz

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract

Let d be a positive integer. Can a given graph G be realized in R^d so that vertices are mapped to distinct points, two vertices being adjacent if and only if the corresponding points lie on a common line that is parallel to some axis? Graphs admitting such realizations have been studied in the literature for decades under different names. Peterson asked in [Discrete Appl. Math., 2003] about the complexity of the recognition problem. While the two-dimensional case corresponds to the class of line graphs of bipartite graphs and is well-understood, the complexity question has remained open for all higher dimensions. In this paper, we answer this question. We establish the NP-completeness of the recognition problem for any fixed dimension, even in the class of bipartite graphs. To do this, we strengthen a characterization of induced subgraphs of 3-dimensional Hamming graphs due to Klavžar and Peterin. We complement the hardness result by showing that for some important classes of perfect graphs –including chordal graphs and distance-hereditary graphs– the minimum dimension of the Euclidean space in which the graph can be realized, or the impossibility of doing so, can be determined in linear time.

Cite as

Martin Milanic, Peter Mursic, and Marcelo Mydlarz. Induced Embeddings into Hamming Graphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{milanic_et_al:LIPIcs.MFCS.2017.28,
  author =	{Milanic, Martin and Mursic, Peter and Mydlarz, Marcelo},
  title =	{{Induced Embeddings into Hamming Graphs}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.28},
  URN =		{urn:nbn:de:0030-drops-81289},
  doi =		{10.4230/LIPIcs.MFCS.2017.28},
  annote =	{Keywords: gridline graph, Hamming graph, induced embedding, NP-completeness, chordal graph}
}

Search Results

Documents authored by Mydlarz, Marcelo

Induced Embeddings into Hamming Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message