Planarization (original) (raw)
In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph. Planarization may be performed by using any method to find a drawing (with crossings) for the given graph, and then replacing each crossing point by a new artificial vertex, causing each crossed edge to be subdivided into a path. The original graph will be represented as an immersion minor of its planarization.
| Property | Value |
|---|---|
| dbo:abstract | In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph. Planarization may be performed by using any method to find a drawing (with crossings) for the given graph, and then replacing each crossing point by a new artificial vertex, causing each crossed edge to be subdivided into a path. The original graph will be represented as an immersion minor of its planarization. In incremental planarization, the planarization process is split into two stages. First, a large planar subgraph is found within the given graph. Then, the remaining edges that are not already part of this subgraph are added back one at a time, and routed through an embedding of the planar subgraph. When one of these edges crosses an already-embedded edge, the two edges that cross are replaced by two-edge paths, with a new artificial vertex that represents the crossing point placed at the middle of both paths. In some case a third local optimization stage is added to the planarization process, in which edges with many crossings are removed and re-added in an attempt to improve the planarization. (en) |
| dbo:wikiPageID | 43170363 (xsd:integer) |
| dbo:wikiPageLength | 9943 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1102259894 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Degree_(graph_theory) dbr:Induced_subgraph dbc:Planar_graphs dbr:Connected_graph dbr:Glossary_of_graph_theory dbr:Graph_minor dbr:Branch_and_cut dbr:NP-hard dbr:Embedding dbr:Path_(graph_theory) dbr:Spanning_tree dbr:Local_search_(optimization) dbr:Dual_graph dbr:Graph_drawing dbr:Graph_theory dbr:Planar_graph dbr:Polynomial_time dbr:Approximation_ratio dbr:SNP_(complexity) dbr:Vertex_(graph_theory) dbr:Partial_k-tree dbr:Random_permutation dbr:Parameterized_complexity dbr:Mathematical dbr:Shortest_path_algorithm |
| dbp:wikiPageUsesTemplate | dbt:Harvtxt dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Planar_graphs |
| gold:hypernym | dbr:Method |
| rdf:type | dbo:Software |
| rdfs:comment | In the mathematical field of graph theory, planarization is a method of extending graph drawing methods from planar graphs to graphs that are not planar, by embedding the non-planar graphs within a larger planar graph. Planarization may be performed by using any method to find a drawing (with crossings) for the given graph, and then replacing each crossing point by a new artificial vertex, causing each crossed edge to be subdivided into a path. The original graph will be represented as an immersion minor of its planarization. (en) |
| rdfs:label | Planarization (en) |
| owl:sameAs | freebase:Planarization yago-res:Planarization wikidata:Planarization https://global.dbpedia.org/id/n2iu |
| prov:wasDerivedFrom | wikipedia-en:Planarization?oldid=1102259894&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Planarization |
| is dbo:wikiPageRedirects of | dbr:Graph_skewness dbr:Maximal_planar_subgraph dbr:Maximal_planar_subgraph_problem dbr:Maximum_planar_subgraph dbr:Maximum_planar_subgraph_problem |
| is dbo:wikiPageWikiLink of | dbr:Petra_Mutzel dbr:Crossing_number_(graph_theory) dbr:Matroid_parity_problem dbr:Graph_minor dbr:Cactus_graph dbr:Block_graph dbr:Planar_graph dbr:Graph_skewness dbr:Maximal_planar_subgraph dbr:Maximal_planar_subgraph_problem dbr:Maximum_planar_subgraph dbr:Maximum_planar_subgraph_problem dbr:List_of_terms_relating_to_algorithms_and_data_structures |
| is foaf:primaryTopic of | wikipedia-en:Planarization |