In a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan- planar drawings such that the vertices are restricted to two distinct horizontal layers and edges are straight-line segments that connect vertices of different layers. We characterize 2-layer fan-planar drawable graphs and describe a linear-time testing and embedding algorithm for biconnected graphs. We also study the relationship between 2-layer fan-planar graphs and 2-layer right-angle crossing graphs.
Algorithms and characterizations for 2-layer fan-planarity: From caterpillar to stegosaurus
BINUCCI, Carla;DIDIMO, WALTER;MONTECCHIANI, FABRIZIO;
2017
Abstract
In a fan-planar drawing of a graph there is no edge that crosses two other independent edges. We study 2-layer fan-planar drawings, i.e., fan- planar drawings such that the vertices are restricted to two distinct horizontal layers and edges are straight-line segments that connect vertices of different layers. We characterize 2-layer fan-planar drawable graphs and describe a linear-time testing and embedding algorithm for biconnected graphs. We also study the relationship between 2-layer fan-planar graphs and 2-layer right-angle crossing graphs.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
JGAA-Binucci+2017.21.1.pdf
accesso aperto
Tipologia di allegato:
PDF-editoriale
Licenza:
Creative commons
Dimensione
617.8 kB
Formato
Adobe PDF
|
617.8 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.