NIC-planar graphs

作者：Bachmaier Christian; Brandenburg Franz J; Hanauer Kathrin^*; Neuwirth Daniel; Reislhuber Josef

来源：Discrete Applied Mathematics, 2017, 232: 23-40.

DOI：10.1016/j.dam.2017.08.015

• NIC-planarity
• Density
• Recognition
• 1-planarity
• Right-angle crossings (RAC)

A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end vertex. NIC-planarity generalizes IC-planarity, which allows a vertex to be incident to at most one crossing edge, and specializes 1-planarity, which only requires at most one crossing per edge.
We characterize embeddings of maximal NIC-planar graphs in terms of generalized planar dual graphs. The characterization is used to derive tight bounds on the density of maximal NIC-planar graphs which ranges between 3.2(n - 2) and 3.6(n - 2). Further, we prove that optimal NIC-planar graphs with 3.6(n - 2) edges have a unique embedding and can be recognized in linear time, whereas the general recognition problem of NIC-planar graphs is NP-complete. In addition, we show that there are NIC-planar graphs that do not admit right angle crossing drawings, which distinguishes NIC-planar from IC-planar graphs.

• 出版日期2017-12-11