Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PLANAR GRAPH:
Reports tagged with planar graph:
TR06-156 | 7th December 2006
Tomas Feder, Rajeev Motwani

#### Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length
$n^{\Omega(1/\log\log n)}$. This is a consequence of a more general
result in which we show that if $G$ has maximum degree $d$ and has a
cycle with $k$ vertices (or a 3-cyclable minor $H$ with $k$ vertices),
then ... more >>>

TR08-011 | 21st November 2007
Kazuo Iwama, Suguru Tamaki

#### The Complexity of the Hajos Calculus for Planar Graphs

The planar Hajos calculus is the Hajos calculus with the restriction that all the graphs that appear in the construction (including a final graph) must be planar. We prove that the planar Hajos calculus is polynomially bounded iff the HajLos calculus is polynomially bounded.

more >>>

TR19-091 | 7th July 2019
Ryo Ashida, Tatsuya Imai, Kotaro Nakagawa, A. Pavan, Vinodchandran Variyam, Osamu Watanabe

#### A Sublinear-space and Polynomial-time Separator Algorithm for Planar Graphs

In [12] (CCC 2013), the authors presented an algorithm for the reachability problem over directed planar graphs that runs in polynomial-time and uses $O(n^{1/2+\epsilon})$ space. A critical ingredient of their algorithm is a polynomial-time, $\tldO(\sqrt{n})$-space algorithm to compute a separator of a planar graph. The conference version provided a sketch ... more >>>

ISSN 1433-8092 | Imprint