Maximum planar subgraphs and nice embeddings: Practical layout tools

DOI10.1007/BF02086607zbMath0854.68073WikidataQ56977494 ScholiaQ56977494MaRDI QIDQ1920420

Michael Jünger, Petra Mutzel

Publication date: 20 October 1996

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

automatic graph drawing; maximum planar subgraph

Mathematics Subject Classification ID

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

Related Items

A simulated annealing algorithm for the maximum planar subgraph problem, Efficient Extraction of Multiple Kuratowski Subdivisions, A branch-and-cut approach to the crossing number problem, Non-planar core reduction of graphs, Advances in the theory and practice of graph drawing, A genetic algorithm for determining the thickness of a graph, 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, A simulated annealing algorithm for determining the thickness of a graph, DRAWING DIRECTED ACYCLIC GRAPHS: AN EXPERIMENTAL STUDY, Computing Maximum C-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