Name
Abstract | ||
|---|---|---|
A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. A graph is maximal 1-planar (1-plane), if we cannot add any missing edge so that the resulting graph is still 1-planar (1-plane). Brandenburg etal. showed that there are maximal 1-planar graphs with only 4517n+O(1)approximate to 2.647n edges and maximal 1-plane graphs with only 73n+O(1)approximate to 2.33n edges. On the other hand, they showed that a maximal 1-planar graph has at least 2813n-O(1)approximate to 2.15n-O(1) edges, and a maximal 1-plane graph has at least 2.1n-O(1) edges. We improve both lower bounds to 20n9 approximate to 2.22n. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1002/jgt.22187 | JOURNAL OF GRAPH THEORY |
Keywords | Field | DocType |
1-planar,edge density | Combinatorics,Edge density,Planar graph,Mathematics | Journal |
Volume | Issue | ISSN |
88.0 | 1.0 | 0364-9024 |
Citations | PageRank | References |
1 | 0.37 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| János Barát | 1 | 1 | 0.71 |
| Géza Tóth | 2 | 72 | 9.25 |