License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.30
URN: urn:nbn:de:0030-drops-80770
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8077/
Go to the corresponding LIPIcs Volume Portal

Casel, Katrin ; Fernau, Henning ; Grigoriev, Alexander ; Schmid, Markus L. ; Whitesides, Sue

Combinatorial Properties and Recognition of Unit Square Visibility Graphs

pdf-format:
LIPIcs-MFCS-2017-30.pdf (0.6 MB)

Abstract

Unit square (grid) visibility graphs (USV and USGV, resp.) are described by axis-parallel visibility between unit squares placed (on integer grid coordinates) in the plane. We investigate combinatorial properties of these graph classes and the hardness of variants of the recognition problem, i.e., the problem of representing USGV with fixed visibilities within small area and, for USV, the general recognition problem.

BibTeX - Entry

@InProceedings{casel_et_al:LIPIcs:2017:8077,
  author =	{Katrin Casel and Henning Fernau and Alexander Grigoriev and Markus L. Schmid and Sue Whitesides},
  title =	{{Combinatorial Properties and Recognition of Unit Square Visibility Graphs}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8077},
  URN =		{urn:nbn:de:0030-drops-80770},
  doi =		{10.4230/LIPIcs.MFCS.2017.30},
  annote =	{Keywords: Visibility graphs, visibility layout,  NP-completeness, exact algorithms}
}

Keywords: Visibility graphs, visibility layout, NP-completeness, exact algorithms
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI