Planar Graph Problems

Introduction to automata theory, languages and computation

1981 • 11,042 citations

Reducibility among Combinatorial Problems

1972 • 10,743 citations

The Design and Analysis of Computer Algorithms

1974 • 9,688 citations

Complexity of Computer Computations

1972 • 2,804 citations

Some simplified NP-complete graph problems

1976 • 2,051 citations

Maximal Flow Through a Network

2009 • 1,942 citations

Theory of graphs

1962 • 1,597 citations

Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

1976 • 1,525 citations

A Separator Theorem for Planar Graphs

1979 • 1,381 citations

The NP-Completeness of Edge-Coloring

1981 • 1,135 citations

Efficient Planarity Testing

1974 • 1,090 citations

A data structure for dynamic trees

1983 • 1,066 citations

Efficient Algorithms for Shortest Paths in Sparse Networks

1977 • 1,039 citations

Introduction to Graph Theory

1972 • 969 citations

Every planar map is four colorable. Part I: Discharging

1977 • 904 citations

Algorithms for drawing graphs: an annotated bibliography

1994 • 859 citations

Integer Programming and Network Flows.

1970 • 709 citations

Applications of a Planar Separator Theorem

1980 • 667 citations

Arboricity and Subgraph Listing Algorithms

1985 • 645 citations

Steiner problem in networks: A survey

1987 • 593 citations

Steiner problem in networks: a survey

1987 • 586 citations

Generalized Nested Dissection

1979 • 561 citations

The Planar Hamiltonian Circuit Problem is NP-Complete

1976 • 515 citations

A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs

1986 • 494 citations

Smallest-last ordering and clustering and graph coloring algorithms

1983 • 492 citations

A theorem on planar graphs

1956 • 485 citations

Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

1987 • 455 citations

Finding a Minimum Circuit in a Graph

1978 • 406 citations

The Complexity of Near-Optimal Graph Coloring

1976 • 314 citations

Bemerkungen zum Vierfarbenproblem.

1936 • 291 citations

Convex Representations of Graphs

1960 • 287 citations

Multicommodity flows in planar graphs

1981 • 284 citations

Planar Graphs: Theory and Algorithms

1988 • 271 citations

Computing an st-numbering

1976 • 261 citations

Finding small simple cycle separators for 2-connected planar graphs

1986 • 258 citations

Graph theory with applications to algorithms and computer science

1985 • 226 citations

On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte

1979 • 221 citations

Send-and-Split Method for Minimum-Concave-Cost Network Flows

1987 • 216 citations

A linear algorithm for embedding planar graphs using PQ-trees

1985 • 206 citations

Edge-colourings of graphs

1977 • 190 citations

Planarity and duality of finite and infinite graphs

1980 • 182 citations

Small sets supporting fary embeddings of planar graphs

1988 • 172 citations

On Edge Coloring Bipartite Graphs

1982 • 170 citations

A theorem on paths in planar graphs

1983 • 161 citations

Algorithms for Edge Coloring Bipartite Graphs and Multigraphs

1982 • 160 citations

The equivalence of theorem proving and the interconnection problem

1975 • 155 citations

On Odd Cuts and Plane Multicommodity Flows

1981 • 141 citations

Edge-colourings of graphs

1978 • 140 citations

Maximum Flow in Planar Networks

1979 • 125 citations

Maximum flow in (s,t) planar networks

1981 • 108 citations

Graph minors. VI. Disjoint paths across a disc

1986 • 103 citations

The hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs

1989 • 100 citations

NP-Completeness of the Hamiltonian Cycle Problem for Bipartite Graphs

1980 • 100 citations

Drawing plane graphs nicely

1985 • 93 citations

Progress in Graph Theory

1984 • 92 citations

Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time

1983 • 92 citations

Edge-disjoint paths in planar graphs

1985 • 89 citations

The complexity of drawing trees nicely

1983 • 89 citations

Routing through a rectangle

1986 • 80 citations

Two-Commodity Flow

1978 • 78 citations

Approximation algorithms for NP-complete problems on planar graphs

1983 • 74 citations

The clique problem for planar graphs

1981 • 60 citations

Bridges and Hamiltonian circuits in planar graphs

1977 • 60 citations

A linear 5-coloring algorithm of planar graphs

1981 • 55 citations

An $O(n\log ^2 n)$ Algorithm for Maximum Flow in Undirected Planar Networks

1985 • 55 citations

Introduction to Graph Theory

2023 • 54 citations

A Depth-First-Search Characterization of Planarity

1982 • 46 citations

Planar Multicommodity Fows, Maximum Matchings and Negative Cycles

1986 • 41 citations

An Efficient Algorithm for Finding Multicommodity Flows in Planar Networks

1985 • 40 citations

An Efficient Cycle Vector Space Algorithm for Listing All Cycles of a Planar Graph

1981 • 38 citations

Multicommodity flows in graphs

1983 • 38 citations

Routing through a generalized switchbox

1986 • 34 citations

A short proof of the two-commodity flow theorem

1979 • 34 citations

An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs

1982 • 32 citations

An approximation algorithm for the hamiltonian walk problem on maximal planar graphs

1983 • 32 citations

On linear-time algorithms for five-coloring planar graphs

1984 • 30 citations

Two commodity network flows and linear programming

1973 • 30 citations

A lower bound for the independence number of a planar graph

1976 • 28 citations

Two linear-time algorithms for five-coloring a planar graph

1980 • 27 citations

The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs

1982 • 26 citations

An upper bound on the length of a Hamiltonian walk of a maximal planar graph

1980 • 25 citations

Finding short cycles in planar graphs using separators

1986 • 25 citations

A theorem on paths in planar graphs

1986 • 24 citations

Finding Steiner forests in planar graphs

1990 • 23 citations

Improved edge-coloring algorithms for planar graphs

1990 • 22 citations

A linear algorithm for finding Hamiltonian cycles in 4-connected maximal planar graphs

1984 • 22 citations

Applications of the Lipton and Tarjan's Planar Separator Theorem

1982 • 22 citations

On multicommodity flows in planar graphs

1984 • 21 citations

On the chromatic index of multigraphs and a conjecture of Seymour (I)

1986 • 17 citations

A Linear Algorithm for Colouring Planar Graphs with Five Colours

1985 • 16 citations

An algorithm for finding a large independent set in planar graphs

1983 • 11 citations

The Klein bottle and multicommodity flows

1989 • 9 citations

Algorithms for multicommodity flows in planar graphs

1989 • 9 citations

Finding an independent set in a planar graph

1974 • 7 citations

An efficient parallel algorithm for computing a large independent set in a planar graph

1991 • 7 citations

The Klein bottle and multicommodity flows

1988 • 1 citations