An efficient graph planarization two-phase heuristic
| Autor: | Olivier Goldschmidt, Alexan Takvorian |
|---|---|
| Rok vydání: | 1994 |
| Předmět: |
Discrete mathematics
Computer Networks and Communications Strength of a graph Butterfly graph Hypercube graph law.invention Combinatorics Graph bandwidth Hardware and Architecture Graph power law Line graph Null graph Software Complement graph MathematicsofComputing_DISCRETEMATHEMATICS Information Systems Mathematics |
| Zdroj: | Networks. 24:69-73 |
| ISSN: | 1097-0037 0028-3045 |
| DOI: | 10.1002/net.3230240203 |
| Popis: | Given a graph G = (V, E), the graph planarization problem is to find a largest subset F of E, such that H = (V, F) is planar. It is known to be NP-complete. This problem is of interest in automatic graph drawing, in facilities layout, and in the design of printed circuit boards and integrated circuits. We present a two-phase heuristic for solving the planarization problem. The first phase devises a clever ordering of the vertices of the graph on a single line and the second phase tries to find the maximal number of nonintersecting edges that can be drawn above or below this line. Extensive empirical results show that this heuristic outperforms its competitors. © 1994 by John Wiley & Sons, Inc. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Plný text