✦ LIBER ✦

An algorithm for drawing planar graphs

✍ Scribed by Bor Plestenjak

Publisher: John Wiley and Sons
Year: 1999
Tongue: English
Weight: 382 KB
Volume: 29
Category: Article
ISSN: 0038-0644
DOI: 10.1002/(sici)1097-024x(199909)29:11<973::aid-spe268>3.0.co;2-b

No coin nor oath required. For personal study only.

✦ Synopsis

A simple algorithm for drawing 3-connected planar graphs is presented. It is derived from the Fruchterman and Reingold spring embedding algorithm by deleting all repulsive forces and fixing vertices of an outer face. The algorithm is implemented in the system for manipulating discrete mathematical structures Vega. Some examples of derived figures are given.

📜 SIMILAR VOLUMES

A GRASP for graph planarization

✍ Resende, Mauricio G. C.; Ribeiro, Celso C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 268 KB 👁 1 views

A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. In this paper, we describe a GRASP for the graph planarization problem, extending the heuristic of Goldschmidt and Takvorian [ Networks 24 (1994) 69-73]. We review the basic concepts of GRASP: co

An extended planar algorithm for maximum

An extended planar algorithm for maximum integral two-flow

✍ Manor, Raanan; Penn, Michal 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 170 KB 👁 1 views

Several problems, including the maximum integral two-flow problem, are known to be NPcomplete, but efficiently solvable for planar graphs. In this paper, we extend the algorithm for maximum integral two-flow in planar graphs to certain undirected K 3,3 -free graphs (graphs not containing any subgrap

Algorithms for coloring semi-random grap

Algorithms for coloring semi-random graphs

✍ C. R. Subramanian; Martin Fürer; C. E. Veni Madhavan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 2 views

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require ␦ Ž . Ž . n ␦ ) 0 colors even for bounded chromatic k-co

Decomposition algorithms for the maximum

Decomposition algorithms for the maximum-weight connected graph problem

✍ Heungsoon Felix Lee; Daniel R. Dooly 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views

Algorithms for graph partitioning on the

Algorithms for graph partitioning on the planted partition model

✍ Anne Condon; Richard M. Karp 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 192 KB 👁 1 views

Simple Markov-chain algorithms for gener

Simple Markov-chain algorithms for generating bipartite graphs and tournaments

✍ Ravi Kannan; Prasad Tetali; Santosh Vempala 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 174 KB 👁 2 views

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in g