Algorithms and characterizations for 2-layer fan-planarity: From caterpillar to stegosaurus
Autor(en): | Binucci, C. Chimani, M. Didimo, W. Gronemann, M. Klein, K. Kratochvíl, J. Montecchiani, F. Tollis, I.G. |
Erscheinungsdatum: | 2017 | Herausgeber: | Brown University | Journal: | Journal of Graph Algorithms and Applications | Volumen: | 21 | Ausgabe: | 1 | Startseite: | 81 | Seitenende: | 102 | Zusammenfassung: | 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. © 2017, Brown University. All rights reserved. |
ISSN: | 15261719 | DOI: | 10.7155/jgaa.00398 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85010972011&doi=10.7155%2fjgaa.00398&partnerID=40&md5=3b861b2225d2de33d1a99707622402c5 |
Zur Langanzeige
Seitenaufrufe
2
Letzte Woche
1
1
Letzter Monat
1
1
geprüft am 03.06.2024