✦ LIBER ✦

A GRASP for graph planarization

✍ Scribed by Resende, Mauricio G. C.; Ribeiro, Celso C.

Publisher: John Wiley and Sons
Year: 1997
Tongue: English
Weight: 268 KB
Volume: 29
Category: Article
ISSN: 0028-3045
DOI: 10.1002/(sici)1097-0037(199705)29:3<173::aid-net5>3.0.co;2-e

No coin nor oath required. For personal study only.

✦ Synopsis

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: construction and local search algorithms. The implementation of GRASP for graph planarization is described in detail. Computational experience on a large set of standard test problems is presented. On almost all test problems considered, the new heuristic either matches or finds a better solution than previously described graph planarization heuristics. In several cases, previously unknown optimal solutions are found.

📜 SIMILAR VOLUMES

An algorithm for drawing planar graphs

✍ Bor Plestenjak 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 382 KB 👁 2 views

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 s

A universal planar graph under the minor

A universal planar graph under the minor relation

✍ Diestel, Reinhard; K�hn, Daniela 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 488 KB 👁 1 views

planar graph that contains every planar graph as a minor.

Maximum-weight-window problem of a plana

Maximum-weight-window problem of a planar graph

✍ Kazuaki Yamaguchi; Ken Kotani; Sumio Masuda; Toshinobu Kashiwabara 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 406 KB

A short proof of Kuratowski's graph plan

A short proof of Kuratowski's graph planarity criterion

✍ Makarychev, Yury 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 2 views

We present a new short combinatorial proof of the sufficiency part of the well-known Kuratowski's graph planarity criterion. The main steps are to prove that for a minor minimal non-planar graph G and any edge xy: (1) G-x-y does not contain θ-subgraph; (2) G-x-y is homeomorphic to the circle; (3)

LINK: a system for graph computation

✍ J. Berry; Nathaniel Dean; Mark K. Goldberg; Gregory E. Shannon; Steven Skiena 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 145 KB

This paper describes the LINK software system, which provides not only a graph editor and graph library, but a computing environment that employs object-oriented Scheme to provide a flexible workbench for algorithm learners and experimenters.

Handedness for grasping objects and decl

Handedness for grasping objects and declarative pointing: A longitudinal study

✍ Anne-Yvonne Jacquet; Rana Esseily; Delphine Rider; Jacqueline Fagard 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 287 KB

## Abstract It is still unclear whether infants become right‐handed because of their left‐hemisphere specialization for language (through gestural communication for instance), whether they speak predominantly with their left hemisphere because of this hemisphere's superiority in controlling sequent