The construction of a dual D(G) can be applied in any plane graph G: draw a...

The construction of a dual D(G) can be applied in any plane graph G: draw a vertex of D(G) in the middle of each region of G and draw an edge e* of D(G) perpendicular to each edge e of G; e* connects the vertices of D(G) representing the regions on either side of e.

a) A dual need not be a graph. It might have two edges between the same pair of vertices or a self-loop edge (from a vertex to itself). find two planar graphs with duals that are not graphs because they contain these two forbidden situations.

C) Show that the degree of a vertex in dual graph D(G) equals the number of boundary edges of the corresponding region in the planar graph G.

E) show for any plane depiction of a graph G that the vertices of G correspond to regions in D(G)

Solutions

Expert Solution

C) In the example we have drawn

degree (w1)= 3, the region (whose middle point is w1 has three boundary edges {v1, v4}, {v1, v2}, {v2, v4},

degree (w2)= 3, the region (whose middle point is w2 has three boundary edges {v2, v4}, {v3, v2}, {v3, v4},

degree (w3)= 4, the region (whose middle point is w3 has four boundary edges {v1, v4}, {v1, v2}, {v2, v3}, {v3, v4},

Observe that degree of each vertex of D(G) and the region bounded by the edges of the region are equal.

E) In the dual graph D(G) has four regions, and the first region has v1 in the interior, the second region has v2 in the interior, the third region has v3 in the interior, and the fourth region has v4 in the interior. Thus the vertices of G correspond to regions in D(G)

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3...

A maximal plane graph is a plane graph G = (V, E) with n ≥ 3 vertices such that if we join any two non-adjacent vertices in G, we obtain a non-plane graph. a) Draw a maximal plane graphs on six vertices. b) Show that a maximal plane graph on n points has 3n − 6 edges and 2n − 4 faces. c) A triangulation of an n-gon is a plane graph whose infinite face boundary is a convex n-gon...

(d) Draw a graph of the indifference curves of someone who could be influenced by either...

(d) Draw a graph of the indifference curves of someone who could be influenced by either of two reference points. (e) Is one of the axioms above violated by those indifference curves? If so, which one? (f) Explain how those indifference curves violate the axiom you identified, by labeling some points on the indifference curves and indicating the exact violation.

Using the Expenditure Model (GDP = C + G + I + NX), draw a graph...

Using the Expenditure Model (GDP = C + G + I + NX), draw a graph that depicts Demand-Pull inflation.

prove by induction that for any simple connected graph G, if G has exactly one cycle...

prove by induction that for any simple connected graph G, if G has exactly one cycle then G has the same number of edges and nodes

1)In a tow dimensional plane draw a graph of y=3x-1 and y=2x^2. 2)Find the roots of...

1)In a tow dimensional plane draw a graph of y=3x-1 and y=2x^2. 2)Find the roots of the equation 2x^2 -3x+1=0 3)If function f(x)=2x^2-3x+1, what the value of x where f(x) reaches its minimum?

Problem 8. A bipartite graph G = (V,E) is a graph whose vertices can be partitioned...

Problem 8. A bipartite graph G = (V,E) is a graph whose vertices can be partitioned into two (disjoint) sets V1 and V2, such that every edge joins a vertex in V1 with a vertex in V2. This means no edges are within V1 or V2 (or symbolically: ∀u, v ∈ V1, {u,v} ∉ E and ∀u,v ∈ V2, {u,v} ∉ E). 8(a) Show that the complete graph K2 is a bipartite graph. 8(b) Prove that no complete graph Kn,...

For Market Analysis Solution: draw graph and label P, Q, D, S, Pe, Qe and name...

For Market Analysis Solution: draw graph and label P, Q, D, S, Pe, Qe and name of market. price, quantity, demand, supply, Pe ?, and Qe ?

There are various systems of accounting that can be applied by any entity while maintaining accounting...

There are various systems of accounting that can be applied by any entity while maintaining accounting system. Fundamentally, there are two systems of accounting viz. cash basis and accrual basis which are directly associated with the type and nature of entity. They have their own pros and cons; however, accrual basis of accounting system is more suitable for business entities from income recognition and measurement point of view. Work sheet is a useful device adopted by accountants to determine financial...

Can the Greek Heroic Code be applied to any or all of these 3 Roman figures...

Can the Greek Heroic Code be applied to any or all of these 3 Roman figures (Aeneas and Romulus and Remus)? Explain. If not, then describe at least 2 elements of what might be called the "Roman Heroic Code".

Draw a class diagram for your monopoly. You can use any visual tools to draw the...

Draw a class diagram for your monopoly. You can use any visual tools to draw the diagram and you need to utilize different relationships between classes, define the attributes and operations of classes. Nothing too complex please. Just the basics.

Subjects