Recognizing and drawing IC-planar graphs
Recognizing and drawing IC-planar graphs
复制标题
DOI：
10.1016/j.tcs.2016.04.026
复制
发表时间：
2015-09
影响因子：
3
通讯作者：
F. Brandenburg;W. Didimo;W. Evans;Philipp Kindermann;G. Liotta;Fabrizio Montecchiani
中科院分区：
文献类型：
--
作者：
F. Brandenburg;W. Didimo;W. Evans;Philipp Kindermann;G. Liotta;Fabrizio Montecchiani
给出了关于平面图与平面图之间关系的新结果。如果图形的每条边最多交叉一次，则该图形为平面图形。一个图形如果能以这样一种方式画出来，它的边只在直角相交。这两类图及其关系在过去几年中得到了广泛的研究，因为它们在计算可读图布局对于分析或设计关系数据集很重要的应用领域中具有相关性。我们研究了ic -平面图，这是一平面图的子族，它允许具有独立交叉点的一平面图(即。（没有两条交叉的边共享端点）。我们证明了每一个ic平面图都可以画出直线RAC图，但这可能需要指数面积。如果我们不需要直角相交，我们可以在线性时间和二次面积上画出每一个具有直线边的ic平面图形。然后研究了图是否为集成电路平面的检验问题。我们证明了这个问题是np困难的，即使图的旋转系统是固定的。在积极的方面，我们描述了一个多项式时间算法，该算法用于测试一个三角形平面图是否与给定的一组形成匹配的边扩充为ic平面。
We give new results about the relationship between1-planar graphsandRACgraphs. A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph isRACif it can be drawn in such a way that its edges cross only at right angles. These two classes of graphs and their relationships have been widely investigated in the last years, due to their relevance in application domains where computing readable graph layouts is important to analyze or design relational data sets. We studyIC-planar graphs, the sub-family of 1-planar graphs that admit 1-planar drawings withindependent crossings(i.e., no two crossed edges share an endpoint). We prove that every IC-planar graph admits a straight-line RAC drawing, which may require however exponential area. If we do not require right angle crossings, we can draw every IC-planar graph with straight-line edges in linear time and quadratic area. We then study the problem of testing whether a graph is IC-planar. We prove that this problem is NP-hard, even if a rotation system for the graph is fixed. On the positive side, we describe a polynomial-time algorithm that tests whether a triangulated plane graph augmented with a given set of edges that form a matching is IC-planar.