We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (beyond-planar graphs is a collective term for the primary attempts to generalize the planar graphs) to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every n-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size O(n)×O(n). Then, we show that every n-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size O(n3)×O(n3). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.
Description
Compact drawings of 1-planar graphs with right-angle crossings and few bends - ScienceDirect
%0 Journal Article
%1 CHAPLICK201950
%A Chaplick, Steven
%A Lipp, Fabian
%A Wolff, Alexander
%A Zink, Johannes
%D 2019
%J Computational Geometry: Theory and Applications
%K journal myown publication
%P 50-68
%R https://doi.org/10.1016/j.comgeo.2019.07.006
%T Compact drawings of 1-planar graphs with right-angle crossings and few bends
%U http://www.sciencedirect.com/science/article/pii/S0925772119301051
%V 84
%X We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (beyond-planar graphs is a collective term for the primary attempts to generalize the planar graphs) to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every n-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size O(n)×O(n). Then, we show that every n-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size O(n3)×O(n3). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.
@article{CHAPLICK201950,
abstract = {We study the following classes of beyond-planar graphs: 1-planar, IC-planar, and NIC-planar graphs. These are the graphs that admit a 1-planar, IC-planar, and NIC-planar drawing, respectively. A drawing of a graph is 1-planar if every edge is crossed at most once. A 1-planar drawing is IC-planar if no two pairs of crossing edges share a vertex. A 1-planar drawing is NIC-planar if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (beyond-planar graphs is a collective term for the primary attempts to generalize the planar graphs) to right-angle crossing (RAC) graphs that admit compact drawings on the grid with few bends. We present four drawing algorithms that preserve the given embeddings. First, we show that every n-vertex NIC-planar graph admits a NIC-planar RAC drawing with at most one bend per edge on a grid of size O(n)×O(n). Then, we show that every n-vertex 1-planar graph admits a 1-planar RAC drawing with at most two bends per edge on a grid of size O(n3)×O(n3). Finally, we make two known algorithms embedding-preserving; for drawing 1-planar RAC graphs with at most one bend per edge and for drawing IC-planar RAC graphs straight-line.},
added-at = {2019-10-02T11:19:59.000+0200},
author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes},
biburl = {https://www.bibsonomy.org/bibtex/24911d603f8503da0ba8e23a0a93f1723/chaplick},
description = {Compact drawings of 1-planar graphs with right-angle crossings and few bends - ScienceDirect},
doi = {https://doi.org/10.1016/j.comgeo.2019.07.006},
interhash = {da930b97585439250cf31d829f61953e},
intrahash = {4911d603f8503da0ba8e23a0a93f1723},
issn = {0925-7721},
journal = {Computational Geometry: Theory and Applications},
keywords = {journal myown publication},
note = {Special Issue on the 34th European Workshop on Computational Geometry},
pages = {50-68},
timestamp = {2019-10-02T11:19:59.000+0200},
title = {Compact drawings of 1-planar graphs with right-angle crossings and few bends},
url = {http://www.sciencedirect.com/science/article/pii/S0925772119301051},
volume = 84,
year = 2019
}