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(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.
Users
Please
log in to take part in the discussion (add own reviews or comments).