A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. The 1-planarity testing problem is NP-complete, even for restricted classes of graphs. We present the first general 1-planarity testing and embedding algorithm, and we experimentally investigate its feasibility in practice. The results suggest that our approach can be successfully applied to graphs with up to 30 vertices, while more sophisticated techniques are needed to attack larger graphs.

An experimental study of a 1-planarity testing and embedding algorithm

Binucci C.;Didimo W.;Montecchiani F.
2020

Abstract

A graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. The 1-planarity testing problem is NP-complete, even for restricted classes of graphs. We present the first general 1-planarity testing and embedding algorithm, and we experimentally investigate its feasibility in practice. The results suggest that our approach can be successfully applied to graphs with up to 30 vertices, while more sophisticated techniques are needed to attack larger graphs.
2020
978-3-030-39880-4
978-3-030-39881-1
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1460477
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact