Maximum planar subgraphs and nice embeddings: Practical layout tools

DOI10.1007/BF02086607zbMath0854.68073OpenAlexW2052400534WikidataQ56977494 ScholiaQ56977494MaRDI QIDQ1920420

Michael Jünger, Petra Mutzel

Publication date: 20 October 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02086607

zbMATH Keywords

automatic graph drawingmaximum planar subgraph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (17)

An algorithmic metatheorem for directed treewidth ⋮ A simulated annealing algorithm for the maximum planar subgraph problem ⋮ A Note on the Practicality of Maximal Planar Subgraph Algorithms ⋮ Unnamed Item ⋮ DRAWING DIRECTED ACYCLIC GRAPHS: AN EXPERIMENTAL STUDY ⋮ A branch-and-cut approach to the crossing number problem ⋮ An experimental comparison of four graph drawing algorithms. ⋮ A tabu search procedure based on a random roulette diversification for the weighted maximal planar graph problem ⋮ Unnamed Item ⋮ Computing Maximum C-Planar Subgraphs ⋮ Efficient Extraction of Multiple Kuratowski Subdivisions ⋮ Non-planar core reduction of graphs ⋮ Advances in the theory and practice of graph drawing ⋮ Unnamed Item ⋮ A simulated annealing algorithm for determining the thickness of a graph ⋮ A genetic algorithm for determining the thickness of a graph ⋮ A Linear-Time Algorithm for Finding Induced Planar Subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph theory applications
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A Cutting Plane Algorithm for the Linear Ordering Problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A New Graph-Theoretic Heuristic for Facility Layout
• Efficient Planarity Testing
• A Strategy for Solving the Plant Layout Problem
• An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem
• An efficient graph planarization two‐phase heuristic
• Provably good solutions for the traveling salesman problem

This page was built for publication: Maximum planar subgraphs and nice embeddings: Practical layout tools