Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

On The Queue Number Of Planar Graphs

János Pach, Fabrizio Frati
2013
Journal Articles

Abstract

We prove that planar graphs have O(log(2) n) queue number, thus improving upon the previous O(root n) upper bound. Consequently, planar graphs admit three-dimensional straight-line crossing-free grid drawings in O(n log(8) n) volume, thus improving upon the previous O(n(3/2)) upper bound.

Official source

János Pach, Fabrizio Frati
2013
Journal Articles

Abstract

Official source

Related concepts (12)

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Outerplanar graph

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two forbidden minors K4 and K2,3, or by their Colin de Verdière graph invariants. They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has degeneracy and treewidth at most 2.

Dual graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e.

Related publications (29)

On The Queue Number Of Planar Graphs

Graph Chatbot

Non-planarity of Markoff graphs mod p

A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS