Planar graphs: Theory and algorithms
From MaRDI portal
Publication:1210706
zbMath0647.05001MaRDI QIDQ1210706
Takao Nishizeki, Norishige Chiba
Publication date: 5 June 1993
Published in: Annals of Discrete Mathematics (Search for Journal in Brave)
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items (68)
The searching over separators strategy to solve some NP-hard problems in subexponential time ⋮ At most single-bend embeddings of cubic graphs ⋮ Simpler Linear-Time Kernelization for Planar Dominating Set ⋮ Planar graphs, Hamilton cycles and extreme independence number ⋮ Building a maximal independent set for the vertex-coloring problem on planar graphs ⋮ A heuristic for the coloring of planar graphs ⋮ Asymptotic dimension of planes and planar graphs ⋮ Uniqueness of equilibria in atomic splittable polymatroid congestion games ⋮ A parallel algorithm for edge-coloring partial k-trees ⋮ How to draw a series-parallel digraph ⋮ Triangle graphs ⋮ Separating translates in the plane: Combinatorial bounds and an algorithm ⋮ Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract) ⋮ Radiocolorings in periodic planar graphs: PSPACE-completeness and efficient approximations for the optimal range of frequencies ⋮ Each maximal planar graph with exactly two separating triangles is Hamiltonian ⋮ On planar perfectly contractile graphs ⋮ Hamiltonicity and colorings of arrangement graphs ⋮ Classes of cycle bases ⋮ Unnamed Item ⋮ Edge-Intersection Graphs of k-Bend Paths in Grids ⋮ Computing orthogonal drawings with the minimum number of bends ⋮ On RAC drawings of 1-planar graphs ⋮ A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid ⋮ Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time ⋮ Parallel approximation schemes for problems on planar graphs ⋮ Drawing \(c\)-planar biconnected clustered graphs ⋮ Simple planar graph partition into three forests ⋮ Rectangular grid drawings of plane graphs ⋮ Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules ⋮ Computing bend-minimum orthogonal drawings of plane series-parallel graphs in linear time ⋮ Planarity for clustered graphs ⋮ Edge Irregular Reflexive Labeling for Some Classes of Plane Graphs ⋮ Planarization of graphs embedded on surfaces ⋮ A strengthened analysis of an algorithm for dominating set in planar graphs ⋮ On-line convex planarity testing ⋮ The growth and form of tunnelling networks in ants ⋮ Maximum flow in directed planar graphs with vertex capacities ⋮ Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey ⋮ Bipartite graphs, upward drawings, and planarity ⋮ Unnamed Item ⋮ Faster computation of the Robinson-Foulds distance between phylogenetic networks ⋮ Orthogonal drawings based on the stratification of planar graphs ⋮ Multiple point visibility and related problems ⋮ Divider-based algorithms for hierarchical tree partitioning. ⋮ The approximation of maximum subgraph problems ⋮ Heuristic for rapidly four-coloring large planar graphs ⋮ Re-embedding a 1-plane graph for a straight-line drawing in linear time ⋮ Transit sets of two-point crossover ⋮ Does contraction preserve triangular meshes? ⋮ Concurrence and three-tangle of the graph ⋮ Rectangular grid drawings of plane graphs ⋮ Upward drawings of triconnected digraphs. ⋮ Small grid drawings of planar graphs with balanced partition ⋮ A modular approach to Sprouts ⋮ A tabu search procedure based on a random roulette diversification for the weighted maximal planar graph problem ⋮ List total colorings of series-parallel graphs ⋮ On the approximation of protein threading ⋮ Orthogonal planarity testing of bounded treewidth graphs ⋮ Cliques and extended triangles. A necessary condition for planar clique graphs ⋮ ON EMBEDDING A GRAPH ON TWO SETS OF POINTS ⋮ Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots ⋮ The entire coloring of series-parallel graphs ⋮ Incremental convex planarity testing ⋮ Parallel approximation schemes for a class of planar and near planar combinatorial optimization problems. ⋮ Monotone drawings of graphs with fixed embedding ⋮ Convex representations of maps on the torus and other flat surfaces ⋮ Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases ⋮ Flow in planar graphs with vertex capacities
This page was built for publication: Planar graphs: Theory and algorithms
