TY - JOUR
T1 - An annotated bibliography on 1-planarity
AU - Kobourov, Stephen G.
AU - Liotta, Giuseppe
AU - Montecchiani, Fabrizio
N1 - Publisher Copyright:
© 2017 Elsevier Inc.
PY - 2017/8
Y1 - 2017/8
N2 - The notion of 1-planarity is among the most natural and most studied generalizations of graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at most another edge. The study of 1-planar graphs dates back to more than fifty years ago and, recently, it has driven increasing attention in the areas of graph theory, graph algorithms, graph drawing, and computational geometry. This annotated bibliography aims to provide a guiding reference to researchers who want to have an overview of the large body of literature about 1-planar graphs. It reviews the current literature covering various research streams about 1-planarity, such as characterization and recognition, combinatorial properties, and geometric representations. As an additional contribution, we offer a list of open problems on 1-planar graphs.
AB - The notion of 1-planarity is among the most natural and most studied generalizations of graph planarity. A graph is 1-planar if it has an embedding where each edge is crossed by at most another edge. The study of 1-planar graphs dates back to more than fifty years ago and, recently, it has driven increasing attention in the areas of graph theory, graph algorithms, graph drawing, and computational geometry. This annotated bibliography aims to provide a guiding reference to researchers who want to have an overview of the large body of literature about 1-planar graphs. It reviews the current literature covering various research streams about 1-planarity, such as characterization and recognition, combinatorial properties, and geometric representations. As an additional contribution, we offer a list of open problems on 1-planar graphs.
KW - 1-planarity
KW - Annotated bibliography
KW - Beyond planar graphs
UR - http://www.scopus.com/inward/record.url?scp=85021792718&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85021792718&partnerID=8YFLogxK
U2 - 10.1016/j.cosrev.2017.06.002
DO - 10.1016/j.cosrev.2017.06.002
M3 - Review article
AN - SCOPUS:85021792718
VL - 25
SP - 49
EP - 67
JO - Computer Science Review
JF - Computer Science Review
SN - 1574-0137
ER -