%0 Journal Article %1 clwz-cd1pg-CGTA19 %A Chaplick, Steven %A Lipp, Fabian %A Wolff, Alexander %A Zink, Johannes %D 2019 %J Computational Geometry: Theory and Applications %K gd-info1 myown %P 50--68 %R 10.1016/j.comgeo.2019.07.006 %T Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends %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(n^3) O(n^3)$. 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{clwz-cd1pg-CGTA19, 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 \emph{1-planar} if every edge is crossed at most once. A 1-planar drawing is \emph{IC-planar} if no two pairs of crossing edges share a vertex. A 1-planar drawing is \emph{NIC-planar} if no two pairs of crossing edges share two vertices. We study the relations of these beyond-planar graph classes (\emph{beyond-planar graphs} is a collective term for the primary attempts to generalize the planar graphs) to \emph{right-angle crossing} (\emph{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) \times 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(n^3) \times O(n^3)$. 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 = {2024-04-29T21:12:31.000+0200}, arxiv = {http://arxiv.org/abs/1609.00321}, author = {Chaplick, Steven and Lipp, Fabian and Wolff, Alexander and Zink, Johannes}, biburl = {https://www.bibsonomy.org/bibtex/2d2c2b1f37aa44753ccdfe7540caf24c4/awolff}, doi = {10.1016/j.comgeo.2019.07.006}, interhash = {da930b97585439250cf31d829f61953e}, intrahash = {d2c2b1f37aa44753ccdfe7540caf24c4}, journal = {Computational Geometry: Theory and Applications}, keywords = {gd-info1 myown}, note = {Special Issue on the 34th European Workshop on Computational Geometry}, pages = {50--68}, pdf = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/pub/clwz-cd1pg-CGTA19.pdf}, slides = {http://www1.pub.informatik.uni-wuerzburg.de/pub/wolff/slides/clwz-cd1pg-GD18-slides.pdf}, timestamp = {2024-04-29T21:12:31.000+0200}, title = {Compact Drawings of 1-Planar Graphs with Right-Angle Crossings and Few Bends}, volume = 84, year = 2019 }