Search Results

Documents authored by Whitesides, Sue


Document
Combinatorial Properties and Recognition of Unit Square Visibility Graphs

Authors: Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid, and Sue Whitesides

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


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.

Cite as

Katrin Casel, Henning Fernau, Alexander Grigoriev, Markus L. Schmid, and Sue Whitesides. Combinatorial Properties and Recognition of Unit Square Visibility Graphs. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{casel_et_al:LIPIcs.MFCS.2017.30,
  author =	{Casel, Katrin and Fernau, Henning and Grigoriev, Alexander and Schmid, Markus L. and Whitesides, Sue},
  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 =	{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.30},
  URN =		{urn:nbn:de:0030-drops-80770},
  doi =		{10.4230/LIPIcs.MFCS.2017.30},
  annote =	{Keywords: Visibility graphs, visibility layout, NP-completeness, exact algorithms}
}
Document
05191 Open Problem Session Report

Authors: Sue Whitesides

Published in: Dagstuhl Seminar Proceedings, Volume 5191, Graph Drawing (2006)


Abstract
This is a report on an informal session intended to stimulate communication and sharing of problems. Hence the attributions and citations may contain inaccuracies, and are certainly not complete.

Cite as

Sue Whitesides. 05191 Open Problem Session Report. In Graph Drawing. Dagstuhl Seminar Proceedings, Volume 5191, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{whitesides:DagSemProc.05191.3,
  author =	{Whitesides, Sue},
  title =	{{05191 Open Problem Session Report}},
  booktitle =	{Graph Drawing},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5191},
  editor =	{Michael J\"{u}nger and Stephen Kobourov and Petra Mutzel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05191.3},
  URN =		{urn:nbn:de:0030-drops-3380},
  doi =		{10.4230/DagSemProc.05191.3},
  annote =	{Keywords: Open problems, graph drawing}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail