文章基本信息

标题：On Visibility Representations of Non-Planar Graphs
本地全文：下载
作者：Therese Biedl ; Giuseppe Liotta ; Fabrizio Montecchiani 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：51
页码：19:1-19:16
DOI：10.4230/LIPIcs.SoCG.2016.19
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A rectangle visibility representation (RVR) of a graph consists of an assignment of axis-aligned 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 NP-hard. 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 1-plane 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 straight-line drawings of 1-plane graphs. These forbidden configurations can be tested for in linear time, and so in linear time we can test whether a 1-plane 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.
关键词：Visibility Representations; 1-Planarity; Recognition Algorithm; Forbidden Configuration