Loading...
Please wait, while we are loading the content...
Similar Documents
Separators in Planar Graphs 5.1 Triangulation 5.2 Weights and Balance 5.3 Fundamental-cycle Separators
| Content Provider | Semantic Scholar |
|---|---|
| Abstract | We say a planar embedded graph is triangulated if each face's boundary has at most three edges. Problem 5.1.1. Provide a linear-time algorithm that, given a planar embedded graph G, adds a set of artificial edges to obtain a triangulated planar embedded graph. Show that the number of artificial edges is at most twice the number of original edges. Let G be a planar embedded graph, and let ↵ be a number between 0 and 1. An assignment of nonnegative weights to the faces, vertices, and edges of G is an ↵-proper assignment if no element is assigned more than ↵ times the total weight. A subpartition of these elements is ↵-balanced if, for each part, the sum of the weights of the elements of that part is at most ↵ times the total weight. Let G be a plane graph. A simple cycle C of G defines a subpartition consisting of two parts, the strict interior and the strict exterior of the cycle. If the subpartition is ↵-balanced, we say that C is an ↵-balanced cycle separator. The subgraph induced by the (nonstrict) interior, i.e. including C, is one piece with respect to C, and the subgraph induced by the (nonstrict) exterior is the other piece. First we give a result on fundamental-cycle separators that are balanced with respect to an assignment of weights only to faces. Lemma 5.3.1 (Fundamental-cycle separator of faces). For any plane graph G, 1 4-proper assignment of weights to faces, and spanning tree T of G such that the 53 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://planarity.org/Klein_separators_in_planar_graphs.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
