Geometric biplane graphs. I: Maximal graphs

DOI10.1007/S00373-015-1546-1MaRDI QIDQ2345511zbMATH OpenOpenAlexFDO

Authors Matias Korman, Inês Matos, Maria Saumell, Rodrigo I. Silveira, Csaba D. Tóth, Alfredo García, Ferran Hurtado, Javier Tejel

Publication date 22 May 2015

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.01275

zbMATH Keywords

\(k\)-connected graphsbiplane graphsgeometric graphsgraph augmentationmaximal biplane graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Connectivity (05C40)

Abstract: We study biplane graphs drawn on a finite planar point set $S$ in general position. This is the family of geometric graphs whose vertex set is $S$ and can be decomposed into two plane graphs. We show that two maximal biplane graphs---in the sense that no edge can be added while staying biplane---may differ in the number of edges, and we provide an efficient algorithm for adding edges to a biplane graph to make it maximal. We also study extremal properties of maximal biplane graphs such as the maximum number of edges and the largest maximum connectivity over $n$-element point sets.

Recommendations

• Geometric biplane graphs. II: Graph augmentation
• On the number of plane geometric graphs
• Drawing graphs in two layers
• scientific article; zbMATH DE number 3845604

Cites work

• Asymptotic enumeration and limit laws of planar graphs
• Augmenting the connectivity of geometric graphs
• Augmenting the connectivity of planar and geometric graphs
• Augmenting the edge connectivity of planar straight line graphs to three
• Biplanar graphs: A survey
• Connectivity augmentation in planar straight line graphs
• Constrained tri-connected planar straight line graphs
• Counting triangulations of planar point sets
• Crossing-Free Subgraphs
• Cyclical edge-connectivity of fullerene graphs and (k,6)-cages
• Fáry's theorem for 1-planar graphs
• Generalized Delaunay triangulation for planar graphs
• Geometric biplane graphs. I: Maximal graphs
• Geometric biplane graphs. II: Graph augmentation
• Geometric Thickness of Complete Graphs
• scientific article; zbMATH DE number 2131198 (Why is no real title available?)
• scientific article; zbMATH DE number 3047038 (Why is no real title available?)
• On generating planar graphs
• On representations of some thickness-two graphs
• Plane geometric graph augmentation: a generic perspective
• Testing bipartiteness of geometric intersection graphs
• The boundary and the shape of binary images

Cited in

(7)

• Note on \(k\)-planar crossing numbers
• The biplanar tree graph
• Geometric biplane graphs. I: Maximal graphs
• Geometric biplane graphs. II: Graph augmentation
• The Mathematics of Ferran Hurtado: A Brief Survey
• On the Biplanarity of Blowups
• On the biplanarity of blowups

This page was built for publication: Geometric biplane graphs. I: Maximal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2345511)