2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth

Angelini, Patrizio; Da Lozzo, Giordano; Forster, Henry; Schneck, Thomas

doi:10.1007/978-3-030-68766-3_32

Benvenuti nell'Anagrafe della Ricerca d'Ateneo

La valutazione delle attività di ricerca che si svolgono nelle università ha assunto un'importanza rilevante sia per l'intero sistema universitario sia all'interno di ogni singolo ateneo. Roma Tre si è quindi dotata di idonei strumenti informativi in grado di supportare al meglio le azioni di monitoraggio e di valutazione delle attività di ricerca svolte nei propri dipartimentied ha realizzato una Anagrafe della Ricerca di Ateneo.

The 2-layer drawing model is a well-established paradigm to visualize bipartite graphs. Several beyond-planar graph classes have been studied under this model. Surprisingly, however, the fundamental class of k-planar graphs has been considered only for k= 1 in this context. We provide several contributions that address this gap in the literature. First, we show tight density bounds for the classes of 2-layer k-planar graphs with k∈ { 2, 3, 4, 5 }. Based on these results, we provide a Crossing Lemma for 2-layer k-planar graphs, which then implies a general density bound for 2-layer k-planar graphs. We prove this bound to be almost optimal with a corresponding lower bound construction. Finally, we study relationships between k-planarity and h-quasiplanarity in the 2-layer model and show that 2-layer k-planar graphs have pathwidth at most k+ 1.

Angelini, P., Da Lozzo, G., Forster, H., & Schneck, T. (2020). 2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.403-419). Springer Science and Business Media Deutschland GmbH.

Titolo:	2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth
Autori:	ANGELINI, PATRIZIO DA LOZZO, GIORDANO Forster Henry Schneck Thomas mostra contributor esterni nascondi contributor esterni
Data di pubblicazione:	2020
Serie:	LECTURE NOTES IN ARTIFICIAL INTELLIGENCE
Citazione:	Angelini, P., Da Lozzo, G., Forster, H., & Schneck, T. (2020). 2-Layer k-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.403-419). Springer Science and Business Media Deutschland GmbH.
Handle:	http://hdl.handle.net/11590/386171
ISBN:	978-3-030-68765-6
Appare nelle tipologie:	4.1 Contributo in Atti di convegno

File in questo prodotto:

Non ci sono file associati a questo prodotto.

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/11590/386171

Citazioni

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.