A Theorem on Planar Graphs
From MaRDI portal
Publication:3231816
DOI10.2307/1992980zbMath0070.18403OpenAlexW4245155377WikidataQ56209819 ScholiaQ56209819MaRDI QIDQ3231816
Publication date: 1956
Full work available at URL: https://doi.org/10.2307/1992980
Related Items (only showing first 100 items - show all)
Guarding rectangular art galleries ⋮ Path partitioning planar graphs of girth 4 without adjacent short cycles ⋮ Spanning Eulerian subgraphs of bounded degree in triangulations ⋮ A unified approach to visibility representations of planar graphs ⋮ Toughness and Hamiltonicity of a class of planar graphs ⋮ Cycles in 4-connected planar graphs ⋮ Every 4-connected line graph of a planar graph is Hamiltonian ⋮ Finding Hamiltonian circuits in arrangements of Jordan curves is NP- complete ⋮ Two-page book embeddings of 4-planar graphs ⋮ Protecting convex sets ⋮ Every 5-connected planar triangulation is 4-ordered Hamiltonian ⋮ Greedy drawings of triangulations ⋮ Graph-theoretical conditions for inscribability and Delaunay realizability ⋮ Chords of longest circuits in locally planar graphs ⋮ Dominating plane triangulations ⋮ The circumference of a graph with no \(K_{3,t}\)-minor ⋮ Hamiltonicity and colorings of arrangement graphs ⋮ Random triangulations of the plane ⋮ The complexity of recognizing tough cubic graphs ⋮ Finding Hamiltonian cycles in Delaunay triangulations is NP-complete ⋮ 2-connected spanning subgraphs with low maximum degree in locally planar graphs ⋮ Tutte cycles in circuit graphs ⋮ Pairs of edge disjoint Hamiltonian circuits in 5-connected planar graphs ⋮ On 2-connected spanning subgraphs with low maximum degree ⋮ Hamiltonian cycles in polyhedral maps ⋮ Intersecting longest paths ⋮ Interval matroids and graphs ⋮ Lower bounds on the cardinality of the maximum matchings of planar graphs ⋮ Bounding tree-width via contraction on the projective plane and torus ⋮ The circumference of a graph with no \(K_{3,t}\)-minor. II ⋮ Algorithms and outerplanar conditions for \(A\)-trails in plane Eulerian graphs ⋮ On regular graphs and Hamiltonian circuits, including answers to some questions of Joseph Zaks ⋮ An update on non-Hamiltonian \(\frac{5}{4}\)-tough maximal planar graphs ⋮ Relationship among triangulations, quadrangulations and optimal 1-planar graphs ⋮ Dynamic graph-based search in unknown environments ⋮ Arc diagrams, flip distances, and Hamiltonian triangulations ⋮ Edge-disjoint Hamilton cycles in 4-regular planar graphs ⋮ The smallest 2-connected cubic bipartite planar nonhamiltonian graph ⋮ When m vertices in a k-connected graph cannot be walked round along a simple cycle ⋮ Subgraphs of graphs on surfaces with high representativity ⋮ On k-path Hamiltonian maximal planar graphs ⋮ Hamiltonian knot projections and lengths of thick knots. ⋮ The matching extendability of surfaces ⋮ Spanning closed walks and TSP in 3-connected planar graphs ⋮ On the obfuscation complexity of planar graphs ⋮ Complete colorings of planar graphs ⋮ Polyhedra with few 3-cuts are Hamiltonian ⋮ Domination of maximal \(K_4\)-minor free graphs and maximal \(K_{2, 3}\)-minor free graphs, and disproofs of two conjectures on planar graphs ⋮ Guthrie's problem: new equivalences and rapid reductions ⋮ Spanning trees with nonseparating paths ⋮ Minimal \(k\)-connected non-Hamiltonian graphs ⋮ Flips in planar graphs ⋮ Non-Hamiltonian triangulations with distant separating triangles ⋮ Extending matchings in planar graphs. IV ⋮ On existence theorems ⋮ Hamiltonian triangulations and circumscribing polygons of disjoint line segments ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ Hamiltonian cycles in 4-connected plane triangulations with few 4-separators ⋮ Hamiltonian cycles through prescribed edges of 4-connected maximal planar graphs ⋮ A note on 3-connected cubic planar graphs ⋮ Pairs of Hamiltonian circuits in 5-connected planar graphs ⋮ What is on his mind? ⋮ A note on traversing specified vertices in graphs embedded with large representativity ⋮ Über n-fach zusammenhängende Eckenmengen in Graphen ⋮ Covering planar graphs with forests ⋮ Pairs of edge-disjoint Hamiltonian circuits ⋮ Spanning trees in 3-connected \(K_{3,t}\)-minor-free graphs ⋮ Connectivity, genus, and the number of components in vertex-deleted subgraphs ⋮ Bridges and Hamiltonian circuits in planar graphs ⋮ Hamiltonian properties of polyhedra with few 3-cuts. A survey ⋮ A new proof that 4-connected planar graphs are Hamiltonian-connected ⋮ Every triangulated 3-polytope of minimum degree 4 has a 4-path of weight at most 27 ⋮ Hamiltonian circuits in prisms over certain simple 3-polytopes ⋮ Matching points with squares ⋮ Metamathematical approach to proving theorems of discrete mathematics ⋮ Maximal Hamiltonian cycles in squares of graphs ⋮ 3-trees with few vertices of degree 3 in circuit graphs ⋮ Long cycles in 4-connected planar graphs ⋮ Maximum bipartite subgraphs of cubic triangle-free planar graphs ⋮ 4-connected polyhedra have at least a linear number of Hamiltonian cycles ⋮ Long cycles through specified vertices in a graph ⋮ On spanning subgraphs of 4-connected planar graphs ⋮ Cycle spectra of contraction-critically 4-connected planar graphs ⋮ Vertex degrees and 2-cuts in graphs with many Hamiltonian vertex-deleted subgraphs ⋮ Vertices of small degree in uniquely Hamiltonian graphs ⋮ A generalization of Tutte's theorem on Hamiltonian cycles in planar graphs ⋮ Hamiltonicity in vertex envelopes of plane cubic graphs ⋮ An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs ⋮ Some remarks on Jaeger's dual-hamiltonian conjecture ⋮ On Hamiltonian cycles in 4- and 5-connected plane triangulations ⋮ A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs ⋮ Surfaces, tree-width, clique-minors, and partitions ⋮ Long cycles in graphs on a fixed surface ⋮ Long cycles in 3-connected graphs ⋮ A survey of the asymptotic behaviour of maps ⋮ Hamiltonian cycles in cubic 3-connected bipartite planar graphs ⋮ The number of cycles in 2-factors of cubic graphs ⋮ Small cycle double covers of 4-connected planar graphs ⋮ Extending matchings in graphs: A survey ⋮ Longest cycles in 3-connected cubic graphs
Cites Work
This page was built for publication: A Theorem on Planar Graphs
