Biedl, Therese ;
Liotta, Giuseppe ;
Montecchiani, Fabrizio
On Visibility Representations of NonPlanar Graphs
Abstract
A rectangle visibility representation (RVR) of a graph consists of an assignment of axisaligned rectangles to vertices such that for every edge there exists a horizontal or vertical line of sight between the rectangles assigned to its endpoints. Testing whether a graph has an RVR is known to be NPhard. In this paper, we study the problem of finding an RVR under the assumption that an embedding in the plane of the input graph is fixed and we are looking for an RVR that reflects this embedding. We show that in this case the problem can be solved in polynomial time for general embedded graphs and in linear time for 1plane graphs (i.e., embedded graphs having at most one crossing per edge). The linear time algorithm uses a precise list of forbidden configurations, which extends the set known for straightline drawings of 1plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1plane graph has an RVR and either compute such a representation or report a negative witness. Finally, we discuss some extensions of our study to the case when the embedding is not fixed but the RVR can have at most one crossing per edge.
BibTeX  Entry
@InProceedings{biedl_et_al:LIPIcs:2016:5911,
author = {Therese Biedl and Giuseppe Liotta and Fabrizio Montecchiani},
title = {{On Visibility Representations of NonPlanar Graphs}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {19:119:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5911},
URN = {urn:nbn:de:0030drops59116},
doi = {10.4230/LIPIcs.SoCG.2016.19},
annote = {Keywords: Visibility Representations, 1Planarity, Recognition Algorithm, Forbidden Configuration}
}
2016
Keywords: 

Visibility Representations, 1Planarity, Recognition Algorithm, Forbidden Configuration 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

2016 