Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871764 | Discrete Applied Mathematics | 2017 | 18 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Christian Bachmaier, Franz J. Brandenburg, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber,