Name
Abstract | ||
|---|---|---|
We study biplane graphs drawn on a finite planar point set $$S$$S in general position. This is the family of geometric graphs whose vertex set is $$S$$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$$n-element point sets. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/s00373-015-1546-1 | Graphs and Combinatorics |
Keywords | Field | DocType |
planar graphs,connectivity | Discrete mathematics,Topology,Combinatorics,Indifference graph,Clique-sum,Chordal graph,Independent set,Pathwidth,1-planar graph,Mathematics,Maximal independent set,Dense graph | Journal |
Volume | Issue | ISSN |
31 | 2 | 1435-5914 |
Citations | PageRank | References |
2 | 0.39 | 13 |
Authors | ||
8 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alfredo García Olaverri | 1 | 52 | 7.81 |
| Ferran Hurtado | 2 | 744 | 86.37 |
| Matias Korman | 3 | 178 | 37.28 |
| Inês Matos | 4 | 16 | 5.10 |
| Maria Saumell | 5 | 58 | 10.50 |
| Rodrigo I. Silveira | 6 | 141 | 28.68 |
| Javier Tejel | 7 | 90 | 13.60 |
| Csaba D. Toth | 8 | 91 | 13.63 |