1 Introduction

Representing planar graphs as contact graphs has been a subject of study for many decades. In such a representation, vertices correspond to geometrical objects, such as line-segments or polygons, while edges correspond to two objects touching in some pre-specified fashion. In this paper, we consider side-contact representations of planar graphs, where vertices are simple interior-disjoint polygons, and adjacencies are non-trivial side-contacts between the corresponding polygons. In the weighted version of the problem, the goal is to find a contact representation of G where the area of the polygon for each vertex is proportional to the weight of the vertex, which is given in advance. We call such a representation a proportional contact representation of G. Such representations often lead to a more compelling visualization of a planar graph than usual node-link representations [6] and have practical applications in cartography, VLSI Layout, and floor-planning. Rectilinear polygons with small number of sides (or corners) are often desirable due to aesthetic, practical, and cognitive requirements. In architectural floor-planning and VLSI design, it is also desirable to minimize the unused area or ‘hole’ in the representation. Therefore we address the problem of constructing a proportional contact representation of a planar graph using rectilinear polygons with few sides, so that the representation contains very little or no unused area. In terms of notation, we say that a contact representation uses k-sided polygons if all polygons used have at most k sides, and that it is hole-free if it contains no unused area.

1.1 Related Work

Contact representations of planar graphs can be dated back to 1936 when Koebe showed that any planar graph has a representation by touching circles [15]. While touching circles or touching triangles [9] provide point-contact representations, side-contact representations have also been considered. For example, Gansner et al. [7] show that 6-sided polygons are sometimes necessary and always sufficient for side-contact representation of any planar graph with convex polygons.

Applications in VLSI or architectural layout design encourage the use of rectilinear polygons in a contact representation that fills a rectangle. In this setting it is known that 8 sides are sometimes necessary and always sufficient [10, 18, 28]. A characterization of the graphs admitting a more restricted rectangle-representation is given by Koźmiński and Kinnen [16] and in the dual setting by Ungar [26]. A similar characterization of graphs having representations with 6-sided rectilinear polygons is given by Sun and Sarrafzadeh [24]. Buchsbaum et al. [6] give an overview on the state of the art concerning rectangle contact graphs.

In the results summarized above, the vertex weights and polygonal areas are not considered. The weighted version of the problem, that of proportional contact representations has applications in cartograms, or value-by-area maps. Here, the goal is to redraw an existing geographic map so that a given weight function (e.g., population) is represented by the area of each country. Algorithms by van Kreveld and Speckmann [17] and Heilmann et al. [11] yield representations with rectangular polygons, but the adjacencies may be disturbed. De Berg et al. describe an adjacency-preserving algorithm for proportional contact representation with at most 40 sides for an internally triangulated plane graph G [3]. This was later improved to 34 sides [14].

The problem has also been studied in the dual settings, where there are weights at the internal faces of a plane graph (instead of the vertices), and the area of faces should be proportional. All planar cubic graphs admit such a drawing [25] as do all planar partial 3-trees [5], but not all planar graphs [21]. Proportional rectilinear drawings with 8-sided polygons can be found for special classes of planar graphs [20], but this approach does not extend to general planar graphs. In a recent paper, Biedl and Velázquez [4] describe the best general result, with an O(nlogn) algorithm for proportional rectilinear drawings of cubic triconnected graphs with 12-sided rectilinear polygons. Translating this back to the primal setting, they show that every maximal planar graph has a proportional contact representation with 12-sided rectilinear polygons.

1.2 Our Contribution

Our main contribution is an improvement from the O(nlogn) algorithm for 12-sided rectilinear polygons [4], with a new algorithm based on Schnyder realizers that runs in O(n) time and provides a proportional contact representation of a maximal planar graph with 10-sided polygons.

We also describe a linear-time algorithm for rectilinear proportional contact representations of planar 3-trees with 8-sided rectilinear polygons and show that this is optimal, as there exist planar 3-trees that require 8-sided polygons. Furthermore, both these constructions yield representation with rectangular outer-boundary. We then show that a maximal outer-planar graph admits a proportional contact representation using rectilinear polygons with 6 sides when the outer-boundary is a rectangle and with 4 sides otherwise. All these representations are hole-free. Finally, we study maximal series-parallel graphs. We show that here hole-free representations are not possible with polygons with O(1) sides. Then we offer two algorithms: One uses 6 sides but contains unused area (which can be made arbitrarily small), while the other one has no holes, but uses polygons with O(Δ) sides, where Δ is the maximum degree.

The rest of the paper is organized as follows. We describe our linear-time algorithm for proportional contact representations of maximal planar graphs in Sect. 2. Section 3 contains a description of our algorithm for planar 3-trees. The results for maximal outerplanar graphs and maximal series parallel graphs are covered in Sects. 4 and 5, respectively. Finally Sect. 6 concludes the paper. In our results, all contact representations use rectilinear polygons, and hence we omit the term “rectilinear” occasionally. A preliminary version of this paper was published in [1].

2 Representations for Maximal Planar Graphs

Here we describe the algorithm for proportional contact representations using 10-sided rectilinear polygons. In this and later constructions, we let P(v) denote the polygon representing a vertex v.

We construct the proportional contact representation of a maximal planar graph using Schnyder realizers [23], which we review briefly. A Schnyder realizer of a maximal plane graph G is a partition of the interior edges of G into three sets T 1, T 2 and T 3 of edges that can be directed so that for each interior vertex v,

  1. (1)

    v has out-degree exactly one in each of T 1, T 2 and T 3, and

  2. (2)

    the counterclockwise order of the edges incident to v is: entering T 1, leaving T 2, entering T 3, leaving T 1, entering T 2, leaving T 3.

These two conditions imply that T i , i=1,2,3 define spanning trees of all the interior vertices and rooted at exactly one exterior vertex such that the edges are directed towards the roots. Schnyder proved that any triangulated planar graph has such a realizer and this can be computed in O(n) time [23].

Theorem 1

Let G=(V,E) be a maximal planar graph and let \(w:V\rightarrow\mathbb{R}^{+}\) be a weight function. Then a hole-free proportional contact representation Γ with respect to w can be constructed in linear time where each vertex of G is represented by a 10-sided rectilinear polygon in Γ, and there is no wasted area.

We prove Theorem 1 by giving a linear-time algorithm to construct such a representation Γ of G, where the polygon P(v) for each vertex v of G has a fixed shape; see Fig. 1. (Some sides of the polygon may be degenerate.) This polygon can be decomposed into four rectangles called foot, leg, bridge and body of the polygon. The region bound by the parallel horizontal lines containing the top and the bottom of the bridge is the bridge-strip, and the foot-strip is defined analogously.

Fig. 1
figure 1

A 10-sided rectilinear polygon with decomposition into foot, leg, bridge and body

Full size image

Let G=(V,E) be a maximal plane graph with the three outer vertices v 1, v 2 and v 3 in counterclockwise order, and let \(w:V\rightarrow\mathbb{R}^{+}\) be a weight function. We first find a Schnyder realizer of G that partitions the interior edges into three trees T 1, T 2 and T 3 rooted at v 1, v 2 and v 3, and with all their edges oriented towards the roots of the trees. We add the external edges (v 2,v 1), (v 3,v 1) to T 1 and (v 3,v 2) to T 2, so that all the edges of G are partitioned into the three trees. For each vertex v of G, let f i (v), i=1,2,3 be the out-neighbor of v in T i .

Let R be a rectangle with area equal to ∑ v∈V w(v). We construct a proportional contact representation Γ of G inside R. Figure 2 gives an example of the construction.

Fig. 2
figure 2

Illustration of the algorithm for proportional contact representation of maximal planar graphs: (a) A maximal planar graph G, (b)–(k) illustration of different steps of the algorithm, and (l) a proportional contact representation of G. Only vertex 8 has 10 sides, since this only happens if a vertex has children in all of T 1,T 2 and T 3. The numbering of the vertices denotes the left-first-search traversal order of the vertices

Full size image

The idea is to draw the polygons such that for each vertex v of G, the edges (v,f i (v)) are realized as follows: the top of the bridge of the polygon P(v) of v is adjacent to the bridge of P(f 1(v)), the left of the foot of P(v) is adjacent to the body of P(f 2(v)) and the bottom of the body of P(v) is adjacent to the foot of P(f 3(v)); see also Fig. 1. If we ensure those adjacencies, then there cannot be any other adjacencies since graph G is maximal planar. Hence we indeed produce a contact representation of the input graph.

We use a parameter λ which will uniformly be the height of the foot and the bridge and the width of the leg for all polygons P(v). There are two conditions on λ:

  1. (1)

    |V|λ<H, i.e., horizontal strips of height λ cannot cover all of R.

  2. (2)

    If the height of foot and bridge and the width of leg and body of P(v) all are exactly equal to λ, then the total area of P(v) should be less than the prescribed area w(v).

Since both conditions yield upper bounds we can choose a small enough λ that complies with them (e.g., λ=min v∈V w(v)/(2H+W) will do.)

The algorithm traverses the plane rooted tree T 1 in a left-first-search and while traversing the tree it constructs the representation from left to right. In this modified depth-first-search we associate two timestamps with each vertex v: the discovery-time d(v) and the completion-time c(v). In the case of a leaf vertex of T 1 we artificially separate d(v) and c(v) to get the strict inequality d(v)<c(v). The sequence of timstamps in the example of Fig. 2 is thus d(2), c(2), d(6), d(3), c(3), d(5), d(4),…,c(7), c(8), d(9), c(9). The algorithm makes use of the following inequalities:

Claim

Let v be an interior vertex. Then:

  1. 1.

    d(w)<d(v)<c(v)<c(w) for a vertex w if and only if w is an ancestor of v in T 1.

  2. 2.

    c(f 2(u))<d(v), i.e., any edge in T 2 goes from right to left with respect to the order within tree T 1.

  3. 3.

    c(v)<d(f 3(v)), i.e., any edge in T 3 goes from left to right with respect to the order within tree T 1.

Proof

The first claim holds because we perform a depth-first search in T 1. The second and third claims follow from the property of Schnyder realizers and can be proved using techniques similar to those in [8]. We briefly sketch the proof of (2) here. Consider the directed path P 1 from v to v 1 in T 1 and the directed path P 2 from v to v 2 in T 2 (which begins with edge (v,f 2(v))). These two paths together with the edge (v 1,v 2) form a cycle C. Any vertex inside C is to the left of v in tree T 1. Due to the property of Schnyder realizers, vertex f 1(f 2(v)) is inside C or an ancestor of v in T 1; either way f 2(v) is left of v with respect to T 1. □

The construction of the cartogram is done with a sweep from left to right in the rectangle R. With each time event d(v) and c(v) for v∈V we associate a construction step that moves the sweep line to the right.

Critical for the construction of a polygon P(v) are three time events.

  • At time c(f 2(v)) the foot of P(v) is initialized by fixing its left side and defining the foot strip.

  • At time d(v) the foot is closed, the leg is introduced and the bridge is initialized by fixing its left side and defining the bridge strip.

  • At time c(v) the area used for foot, leg and bridge is computed and the body using the rest of w(v) is constructed.

At any time t, we have a number of foot strips, not yet completed into feet, that are adjacent to each other, hence forming a pile of foot strips at the bottom of rectangle R. Likewise, there is a pile of bridge strips near the top of the rectangle. We maintain the following invariant for these piles:

  1. I1

    The pile of foot strips at time t contains all vertices u with c(f 2(u))<t<d(u) (or u=v 2) and is sorted top-to-bottom by d(u).

  2. I2

    The pile of bridge strips at time t contains all vertices u with d(u)<t<c(u) and is sorted bottom-to-top by c(u).

To initialize the sweep we first definine the polygon P(v 1) as a strip of height w(v 1)/W at the top edge of R. We consider this strip to be the bridge strip of v 1. We also initialize a foot strip for v 2 at the bottom of R. It is easy to verify that the invariants are satisfied.

Action at Time t=d(v):

Known properties: By Claim (2) we have c(f 2(v))<d(v), so by Invariant (I1) vertex v has a foot strip and it is at the top of the foot-strip pile. By Invariant (I2) and Claim (1) vertex f 1(v) has a bridge-strip, and it is the lowest bridge-strip.

Construction: Insert the leg of v between the lower edge of the foot strip of v and the lower edge of the bridge strip of f 1(v). Remove the foot strip of v and add a new bridge strip for v below the bridge strip of f 1(v). Advance the sweep to the right side of the leg of v.

Verification of Invariant: (I1) holds because it held before and we removed the top foot-strip, which was for the one vertex that was discovered. Invariant (I2) holds because we added a bridge-strip for v below that of f 1(v) and c(v)<c(f 1(v)).

Example: Figure 2(i) shows a typical action of this type. At time d(8) the leg is inserted between the existing foot strip and the new bridge strip of 8. Figure 2(c) and (e) show the status after d(6) and d(5). In Fig. 2(f) and (j) the discovery and completion for vertices 4 and 7 are combined in the illustration.

Action at Time c(v):

Known properties: By Invariant (I2) v has a bridge strip and it is the lowest in the pile of bridge strips. We also claim that vertex f 3(v) has a foot strip. Observe that both v and f 2(f 3(v)) are left of f 3(v) in T 1 by Claim (2) and (3). Since (v,f 3(v)) comes after (f 2(f 3(v),f 3(v))) in the clockwise order around f 3(v), we have that v cannot be left of f 2(f 3(v)). In other words c(f 2(f 3(v)))<c(v), so f 3(v) has a foot strip by Invariant (I1). Also the foot strip of f 3(v) is the topmost on the foot strip pile: Any other vertex w with c(v)<d(w)<d(f 3(v)) (and only those could be higher on the foot strip pile by Invariant (I1)) must be between v and f 3(v) in T 1. But then f 2(w) cannot be completed yet, else edge (f 2(w),w) would cross edge (v,f 3(v)).

Construction: Complete the bridge of v by filling the bridge strip up to the current position of the sweep line. Let a(v) be the area used for foot, leg and bridge of v. Let h(v) be the distance between the top edge of the bridge strip of v and the top edge of the foot strip of f 3(v). Insert the body of v as a rectangle of height h(v) and width \(\frac{w(v)-a(v)}{h(v)}\). Advance the sweep to the right side of the body of v. Assign the foot strips to the children of v in T 2. The strips are piled on top of the foot strip of f 3(v) such that the counterclockwise order at v corresponds to the bottom to top order of the strips.

Verification of Invariant: Invariant (I2) holds because it held before and we removed the bottom bridge-strip, which was for the one vertex v that was completed. Invariant (I1) holds because we added a bridge-strip for all children of v in T 2. To show that the order of bridge-strips is correct, observe that the discovery times of children of v in T 2 is increasing in clockwise order. For any two consecutive children c 1,c 2 in T 2 are connected by an edge since G is maximal planar, and the edge is either directed c 1←c 2 and in T 1 or it is directed c 1→c 2 and in T 3 by the property of Schnyder realizers. Therefore either c 1=f 1(c 2) or c 2=f 3(c 1); either way we know that d(c 1)<d(c 2) by Claim (2) and (3).

Example: Figure 2(b) shows the situation after c(2). The polygon P(v 2) is completed and foot strips for the children of v 2 in T 2 have been assigned. Figure 2(d), (f), (g), (j), (k), and (l) show the status after c(3), c(4), c(5), c(6), c(7), c(8), and c(9) respectively.

Recall that the choice of the λ value implies |V|λ<H. Since at any time any vertex has at most one strip reserved for it, it follows that the lowest bridge remains above the highest foot. So there is always vertical space for legs and bodies. To see that there is horizontal space note that at time c(v) the free space to the right of the body of v between all the bridge strips and foot strips has area at least ∑ u:c(v)<d(u) w(u). Together with the invariants for the action steps, this implies that the algorithm runs correctly and that polygons of different vertices only intersect along boundaries. Since the area of R equals w(V) the layout covers all of R so that there is no white-space.

Note that if v is a leaf in T 1, then d(v) and c(v) immediately follow each other. In this case the right edge of the leg and the left edge of the body coincide so that we can merge the two and the shape of P(v) simplifies to body plus foot and only has 6 corners. Another case where P(v) has lower complexity is when f 2(v) and v are siblings in T 1. In this case d(v) follows immediately after c(f 2(v)) and the leg of v is introduced right after the initialization of the foot. Hence P(v) consists of leg, bridge and body and has at most 8 corners.

A Schnyder realizer of a triangulation can be computed in linear time. Since the layout algorithm only performs a constant number of operations per edge of the graph, the overall running time of the algorithm is linear.

So we have now established that 10 sides are sufficient for proportional contact representation with rectilinear polygons. Yeap and Sarrafzadeh [28] gave an example of a maximal planar graph, which is also a planar 3-tree, for which at least 8-sided polygons are necessary. In very recent work [2] (which appeared after the first appearance of the present paper) we prove that 8-sided polygons are also sufficient. However, in contrast to the 10-gon construction given above, the proof of this result is not constructive, and the representation can be found only via numerical approximation. That is, while the algorithm for representation with 10-sided polygons described here can be implemented in linear time and guarantees no cartographic error, realizing all regions with 8-sided polygons and no cartographic error is computationally very expensive (the best approaches are exponential in the number of vertices [12, 27]).

3 Representations of Planar 3-trees

Here we describe proportional contact representations of planar 3-trees with fewer sides (8) in each polygon. A 3-tree is either a 3-cycle or a graph G with a vertex v of degree three in G such that G−v is a 3-tree and the neighbors of v are adjacent. If G is planar, then it is called a planar 3-tree. A plane 3-tree is a planar 3-tree along with a fixed planar embedding of it. It is easy to see that starting with a 3-cycle, any planar 3-tree can be formed by recursively inserting a vertex inside a face and adding an edge between the newly added vertex and each of the three vertices on the face [5, 19].

Using this simple construction, we can create in linear time a representative tree for G [19], which is a rooted ternary tree T G spanning all the internal vertices of G. The root of T G is the first vertex we have to insert into the face of the three outer vertices. Adding a new vertex v in G will introduce three new faces belonging to v. The first vertex w we add in each of these faces will be a child of v in T G . Note that for a planar 3-tree, a representative tree is an equivalent structure as the 4-block tree defined by Kant [13]. For any vertex v of T G , we denote by U v , the set of the descendants of v in T G including v. The predecessors of v are the neighbors of v in G that are not in U v . Clearly each vertex of T G has exactly three predecessors and up to three children. For any vertex set V′, use w(V′) to denote the sum of weights of vertices in V′. Now we have:

Lemma 1

Let G=(V,E) be a plane 3-tree with outer-face {a,b,c} in counter-clockwise order, and let \(w:V\rightarrow\mathbb{R}^{+}\) be a weight function. Let \(\mathcal{R}\) be any rectangle of area w(V−{a,b,c}). Then G−{a,b,c} has a hole-free proportional contact representations with 8-sided rectilinear polygons inside \(\mathcal{R}\). Furthermore, in this representation a vertex v touches the top/left side of \(\mathcal{R}\) if and only if v is adjacent to a/b in G, and it touches the bottom or right side of \(\mathcal{R}\) if and only it is adjacent to c in G. This representation can be obtained in linear time.

Proof

We proceed by induction on |V|. If G has 3 vertices, then it consists of only {a,b,c} and the claim is vacuously true since G−{a,b,c} is empty. Now let |V|≥4. Let v be the unique vertex that is adjacent to {a,b,c} and let u ab ,u bc and u ca be its children in the representative tree T G (some of them may be empty), where the subscript denotes the neighbors that the child shares with v. Cut a rectangle R ca from the right of \(\mathcal{R}\) of area \(w(U_{u_{ca}})\). Cut a rectangle R bc from the bottom left of \(\mathcal{R}\) of area \(w(U_{u_{bc}})\). Cut a rectangle R ab from the top left of \(\mathcal{R}\) of area \(w(U_{u_{ab}})\); see also Fig. 3(a). Since \(U_{u_{ab}}, U_{u_{bc}}, U_{u_{bc}}\) partitions the vertices in V−{v,a,b,c}, this can be done so that rectangles are disjoint. Assign the rest of \(\mathcal{R}\) to be P(v); by construction it has at most 8 sides. Note that if some of \(U_{u_{ab}},U_{u_{bc}},U_{u_{ca}}\) are empty, then the corresponding rectangles are empty and hence P(v) may have fewer than 8 sides.

Fig. 3
figure 3

Illustration for the proof of Lemma 1

Full size image

The graph G ab inside the triangle {a,b,v} is a plane 3-tree with outer-face {a,b,v} and inner vertices \(U_{u_{ab}}\). Since R ab has area \(w(U_{u_{ab}})\), by induction we can find a contact representation of G ab −{a,b,v} that fits inside R ab . Moreover, a vertex is at the top/left side only if it is adjacent to a/b and at the bottom or right side only if it is adjacent to v. Since R ab is at the top left corner of R, placing the drawing of G ab −{a,b,v} inside R ab creates the correct adjacencies with v and satisfies the required conditions for the contact representation of G. Similarly, we have by induction a contact representations for the graph induced by \(U_{u_{ca}}\) that we can place inside R ca . For u bc , we also use induction, but v takes on the role of c while {b,c} take on the role of {a,b}, and we rotate the obtained contact representation clockwise by 90∘. Pasting these three representations of the three smaller graphs into the rectangles reserved for them then gives the desired contact representation of G.

The inductive argument implies a recursive algorithm to find the drawing. To see that it can be implemented in linear time, we pre-compute w(U v ) for any vertex v∈T G by traversing T G bottom-up and adding weights. Since the polygon representing each vertex v of G can be computed in constant time, the time complexity for constructing the representation of G is linear. □

After applying the lemma to G with an arbitrary rectangle \(\mathcal{R}\) of appropriate size, we obtain a representation of the whole graph by adding rectangles of correct area for a and b to the top/left of \(\mathcal{R}\) and a 6-sided polygon for c on the right and below; see Fig. 3(b). Figure 4(b)–(g) illustrates our construction for the planar 3-tree in Fig. 4(a).

Fig. 4
figure 4

Illustration of the algorithm for proportional contact representation of planar 3-trees. The numbering of the vertices represents the insertion order of the vertices

Full size image

The upper bound of 8 sides per polygon is also matched by the corresponding lower bound with a planar 3-tree for which at least 8-sided polygons are necessary in a contact representation with rectilinear polygons [28]. We thus have the following result.

Theorem 2

Polygons with 8 sides are always sufficient and sometimes necessary for hole-free proportional contact representations of planar 3-trees with rectilinear polygons.

4 Representations for Maximal Outer-planar Graphs

Here we describe proportional contact representations of maximal outer-planar graphs with even fewer sides (6 and 4) in each polygon. An outer-planar graph is a graph that has an outer-planar embedding, i.e., a planar embedding with every vertex in the outer face. An outer-planar graph to which no edges can be added without violating outer-planarity is a maximal outer-planar graph. It is easy to see that each internal face in an outer-planar embedding of a maximal outer-planar graph is a triangle, and for n≥3 the outer-face is a simple cycle containing all vertices. We will give a linear-time algorithm to construct a proportional contact representation of a maximal outer-planar graph with rectangles. Before that, we need the following definitions.

Let Γ be a contact representation using rectangles for vertices (but with the outside not necessarily a rectangle). Let B be the bounding box of Γ. We say that a vertex v occupies the top of a representation Γ if there exists a horizontal line ℓ such that the rectangle representing v is exactly the intersection of B with the upper half-space of ℓ. In other words, the rectangle of v contains all of the top end of the bounding box of Γ. Similarly we define that a vertex v occupies the right of Γ.

Lemma 2

Let G be a maximal outer-planar graph, and let (s,t) be an edge on the outer-face, with s before t in clockwise order. Then in linear time we can compute a hole-free proportional contact representation Γ with rectangles for G such that s occupies the top of Γ and t occupies the right of Γ−s.

Proof

We prove the existence of Γ by induction on the number of vertices of G. In the base case, G is a single edge (s,t). To construct Γ, we use an arbitrary rectangle P(s) of area w(s) for s and a rectangle P(t) for t with area w(t) and width smaller than P(s). We place P(t) so that its top right corner coincides with the bottom right corner of P(s). It is easy to verify that all conditions hold for the resulting representation Γ.

For the induction step we assume that G has at least 3 vertices. Let x be the (unique) third vertex on the inner face that is adjacent to (s,t). Then graph G can be split into two graphs at vertex x and edge (s,t): G[s,x] consists of the graph induced by all vertices between s and x in counter-clockwise order around the outer-face, and G[x,t] consists of the graph induced by the vertices between t and x.

By induction G[s,x] has hole-free proportional contact representation with rectangles, where s occupies the top and x occupies the right after removing s. Let Γ s be what remains of this representation after removing s. Likewise, G[x,t] has hole-free proportional contact representation with rectangles, where x occupies the top and t occupies the right after removing x. Let Γ t be what remains of this representation after removing x and t. We now explain how to merge Γ s and Γ t and add s and t such that the resulting drawing satisfies all requirements; see also Fig. 5.

Fig. 5
figure 5

Combining the drawings of two subgraphs

Full size image

Scale the width of Γ t until the bounding box of Γ t is less wide than the rectangle of x in Γ s . To maintain a proportional contact representation, scale the height of Γ t by the inverse of the scale-factor for the width. Now Γ t can be attached at the bottom right end of the representation of x in Γ s . Add a rectangle for t on the right that spans the whole height (and extends below it at the bottom), and make its width such that its area is as prescribed for t. Add a rectangle for s such that it spans the whole width (and extends past it to the left), and make its height such that its area is as prescribed for s. This gives the desired representation without holes.

The above induction proof naturally gives rise to a recursive algorithm to find Γ. We now show that this algorithm can be implemented in linear time. In order to do this, we make sure that all coordinates in the representation are scaled at most once. Let T be the dual graph of G minus the vertex for the outer-face; it is easy to see that T is a tree with maximum degree three. Let the root of T be the vertex that corresponds to the inner face {s,x,t}; then the subtrees of T correspond to the dual trees of the subgraphs. Rather than re-scaling Γ t at each recursive step, we only re-scale the bounding box of Γ t and store at the node of T that represents G[t,x] the scale-factors for the width and height that must be applied to all nodes in Γ t . At the end of the algorithm a linear-time top-down traversal finds the scaling factor for each vertex v of T by multiplying all the scaling factors stored along the path from v x to v. Then with another linear-time top-down traversal of T we can compute the coordinates of all the points in Γ, which concludes the construction. □

Figure 6(b) illustrates a proportional contact representation of the maximal outerplanar graph in Fig. 6(a) with rectangles, computed by the algorithm above. Since a rectangle is a rectilinear polygon with the fewest sides possible, the representation obtained by this algorithm is also optimal. However, the outer boundary of the representation obtained by our construction has size Θ(n). It was already known that the outer-face cannot be a rectangle if the vertices are rectangles [22], but we improve this to a stronger result:

Fig. 6
figure 6

(a) A maximal outerplanar graph G, (b) a proportional contact representation of G with rectangles

Full size image

Lemma 3

There exists a maximal outer-planar graph for which any contact representation with rectangles requires Ω(n) sides on the outer-face.

Proof

Consider any maximal outer-planar graph G such that ⌊n/2⌋ vertices have degree two (any maximal outer-planar graph whose inner dual is a full binary tree suffices). Suppose Γ is a proportional contact representation of G with rectangles. Since rectangles are convex, no two of them can share two sides. Therefore any vertex v of degree 2 shares at most two of its sides with other vertices, and so at least two of its sides with the outer boundary of Γ. Furthermore, these two sides must be consecutive on P(v); otherwise v would be a cut vertex in G. The common endpoint of these two sides is then a corner of the outer boundary of Γ, so the outer-face has at least ⌊n/2⌋ sides. □

Lemma 3 implies that there exist outer-planar graphs for which any contact representation with an outer-boundary of constant size requires at least one of the polygons to have at least six sides. With the following lemma we show that this lower bound of six sides can also be matched with any given weights.

Lemma 4

Let G=(V,E) be a maximal outer-planar graph and let \(w:V\rightarrow\mathbb{R}^{+}\) be a weight function. Then G has a hole-free proportional contact-representation Γ with 6-sided rectilinear polygons such that the outer-boundary of Γ is a rectangle. It can be computed in linear time.

Proof

It is quite straightforward to prove this by analyzing the structure of an outer-planar graph, but it also follows from two earlier results in this paper. We will sketch the second approach.

First, if G is maximal outer-planar, then we can add one vertex v 0 to it that is adjacent to all others. Then create a Schnyder realizer such that v 0 is the root of tree T 1. Then all of v 0’s incident edges are in T 1, which means that all other vertices are leaves in tree T 1. Apply our construction from Sect. 2. From the discussion at the end of Sect. 2, vertices that are leaves in T 1 are drawn with 6-gons in this construction. Omitting the added vertex v 0 (which is a rectangle that spans the top) yields the desired representation.

As a second proof, observe that G′=G∪v 0 is also a 3-tree, and moreover, any vertex v has at most two children in the representative tree T G′ of G′. Apply the construction of Sect. 3, but choose the rectangles for the non-empty children of v in such a way that P(v) has at most 6 sides; one can verify that this is always possible regardless of which child of v is missing. □

Summing up all the results in this section, we have the following theorem.

Theorem 3

For hole-free proportional contact representations of a maximal outer-planar graph, rectangles are always sufficient and necessary, and six-sided polygons are sometimes necessary (and always sufficient) when the outer-boundary has a constant number of sides.

5 Representations for Maximal Series-Parallel Graphs

In the previous sections we studied planar 3-trees (which are the same as maximal planar graphs of treewidth 3) and maximal outerplanar graphs (which are a strict subset of maximal planar graphs of treewidth 2). What can be said about the maximal planar graphs of treewidth 2? These are the same as the so-called maximal series-parallel graphs (defined formally below.) Since for both maximal outer-planar graphs and planar 3-trees we can obtain hole-free proportional contact representations with constant polygon-complexity, one would expect that this also holds for maximal series-parallel graphs. Surprisingly, this is not the case.

We first define these graphs. A series-parallel graph is a graph G that has two terminals s and t, and either G is an edge (s,t), or it has been obtained with one of the following two operations: (1) (Parallel combination) G consists of two or more series-parallel graphs that all have the terminals s and t. (2) (Combination in series) G consists of two series-parallel graphs, one with terminals s and some other vertex x, and the other with terminals x and t. As usual, a maximal series-parallel graph is a series-parallel graph to which we cannot add any more edges and maintain that the resulting graph has no multi-edge and is still a series-parallel graph.

Now let \(K_{2,n}^{+}\) be the graph that consists of two adjacent vertices {s,t}, which are adjacent to all of n vertices x 1,…,x n . In other words, this is K 2,n with an added edge between the two vertices of the size-2 set. Clearly \(K_{2.n}^{+}\) is a maximal series-parallel graphs.

Lemma 5

In any hole-free contact representation of \(K_{2,n}^{+}\), there exists a vertex whose polygon has at least 2n sides.

Proof

Let Γ be a contact representation of \(K_{2,n}^{+}\). Observe that P(x i ) can be on the outerface boundary of Γ for at most two x i ’s, otherwise we could create an outer-planar drawing of K 2,3, an impossibility. Let Γ′ be Γ after removing any P(x i ) that is on the outer-face of Γ.

There are at least n−2 x i ’s left. For each of them, P(x i ) is a rectilinear polygon with at least four corners, and P(x i ) is surrounded by P(s) and P(t). Therefore for every corner of P(x i ) there is a corner in P(s) or P(t). (Note that this holds even if some P(x i ) and P(x j ) meet at a corner: In this case there must be two corners of P(s) and/or P(t) here as well to avoid a non-zero-length contact between P(x i ) and P(x j ).)

This gives at least 4n−8 corners for s and t. If not both s and t are on the outer-face of Γ′, then no x i can have been on the outer-face of Γ, and so there are 4n corners for s and t. If both s and t are on the outer-face of Γ′, then the outer-face boundary gives 8 more corners that have not been counted yet: 4 since any rectilinear polygon has at least 4 corners, and 4 where the boundaries of P(s) and P(t) meet at the outerface boundary of Γ′. Either way, P(s) and P(t) together have at least 4n corners and the claim holds. □

So we cannot hope for no holes and constant complexity of polygons for series-parallel graphs. We now show that if either one of those restrictions are dropped, then proportional contact representations are possible.

5.1 Representations with Arbitrarily Small Holes

We first show that if we allow holes, even of arbitrarily small area, then we can represent series-parallel graphs using 6-gons. Recall that w(V′) means the total weight in vertex set V′. For any graph G, use w(G) to denote w(V(G)).

Lemma 6

Let G be a maximal series-parallel graph with terminals s,t and let \(w:V\rightarrow\mathbb{R}^{+}\) be a weight-function. Let ε>0 be arbitrarily small. Let \(\mathcal{R}\) be any rectangle of area w(V−{s,t})+ε. Then G−{s,t} has a proportional contact representation inside \(\mathcal{R}\) such that a vertex v touches the top/right side of \(\mathcal{R}\) if and only if v is adjacent to s/t in G. Furthermore, this representation can be computed in linear time in the number of vertices in G.

Proof

We prove this by induction on the number of vertices. In the base case, G consists of edge (s,t) only, and the claim is vacuously true since G−{s,t} is empty. So now assume that G has at least 3 vertices. Since G is a maximal series-parallel graph, edge (s,t) must exist. Therefore G must be obtained in a parallel combination of subgraphs G 0,G 1,…,G k , all with terminals s and t. (We assume, without loss of generality, that the naming is such that G 0 is the edge (s,t).) We make k as large as possible, i.e., each subgraph G i for i>0 is obtained in a combination in series of subgraphs \(G_{i}^{s}\) and \(G_{i}^{t}\), where \(G_{i}^{s}\) has terminals s and x i and \(G_{i}^{t}\) has terminals x i and t. The idea is to assign rectangles to each of these subgraphs \(G_{i}^{\alpha}\) (for i=1,…,k and α∈{s,t}) and place the drawings inside \(\mathcal{R}\) appropriately. Let \(V_{i}^{\alpha}=V(G_{i}^{\alpha})-\{x_{i},\alpha\}\). We proceed as follows:

  1. 1.

    First, remove a (very slim) rectangle that spans the left side of \(\mathcal{R}\) and has area ε′:=ε/(5k+2).Footnote 1

  2. 2.

    From the rectangle that remains, remove a very slim rectangle of area ε′ that spans the bottom.

  3. 3.

    From the rectangle that remains, remove an L-shaped 6-sided polygon P(x k ) that spans the bottom and the left side. Choose the side-lengths such that P(x k ) has area w(x k ).

  4. 4.

    From the rectangle that remains, remove a rectangle that spans the left side. Choose its width such that its area is \(w(V_{k}^{s})+2\varepsilon'\). Then split it horizontally so that the rectangle below has area ε′ while the rectangle \(R_{k}^{s}\) above has area \(w(V_{k}^{s})+\varepsilon'\).

  5. 5.

    From the rectangle that remains, remove a very slim rectangle of area ε′ that spans the left side.

  6. 6.

    From the rectangle that remains, remove a rectangle \(R_{k}^{t}\) that spans the bottom. Choose its width such that its area is \(w(V_{k}^{t})+\varepsilon'\).

  7. 7.

    Repeat steps 2–6 for k−1,k−2,k−3,…,1.

  8. 8.

    By choice of ε′ and the areas for all rectangles and L-shapes, all that remains of \(\mathcal{R}\) after removing rectangle \(R_{1}^{t}\) is a slim rectangle (adjacent to the top of \(R_{1}^{t}\)) of area ε′.

Figure 7 illustrates the construction. Note that for each rectangle \(R_{i}^{\alpha}\), two sides are adjacent to empty space, one side is adjacent to x i , and the other side is adjacent to the boundary of \(\mathcal{R}\) where terminal α will be located. Furthermore, \(R_{i}^{\alpha}\) has weight \(w(V_{i}^{\alpha})+\varepsilon'\). Hence by induction \(G_{i}^{\alpha}\) has a proportional contact representation inside rectangle \(R_{i}^{\alpha}\). Moreover, neighbours of the terminals of \(G_{i}^{\alpha}\) are at the top and right. If we flip this contact representation horizontally (or in the case of α=t, rotate \(R_{i}^{\alpha}\) before applying induction, then rotate the resulting contact representation), then placing these contact representations inside the rectangles gives the desired proportional contact representation for G−{s,t}.

Fig. 7
figure 7

The construction for a series-parallel graph. k=3 in this example. Small numbers indicate in which step this rectangle was added

Full size image

As usual the inductive argument can be turned into a recursive algorithm. To see that the computation takes linear time, first observe that steps 2–6 are repeated k times where k is in the order of the degree of s and t outside any \(G_{i}^{\alpha}\) for i=1,…,k and α∈{s,t}. Thus if we count the total number of times these steps are run, this number will be O(∑ v∈V deg(v))=O(n), where n is the number of vertices in G. □

We have thus shown that 6 sides are sufficient for series-parallel graphs, as long as (arbitrarily small) holes are allowed. To see that 6 sides are necessary, consider \(K_{2,4}^{+}\). No matter what embedding we choose, there will always be a vertex that is enclosed by a triangle in \(K_{2,4}^{+}\). Since three rectangles cannot enclose a non-zero area, this shows that \(K_{2,4}^{+}\) requires 6 sides in any contact representation, even if holes are allowed. We hence have the following theorem:

Theorem 4

6 sides are always sufficient and sometimes necessary for proportional contact representations of maximal series-parallel graphs with arbitrarily small holes.

5.2 Hole-free Representations with Many Corners

We now show how with a different invariant for placing vertices, we can create proportional contact representations of series-parallel graphs that have no holes (but many corners for polygons.)

Lemma 7

Let G be a maximal series-parallel graph with terminals s,t, and let \(w: V\rightarrow\mathbb{R}^{+}\) be a weight-function. Let \(\mathcal{R}\) be any rectangle of area w(V). Then G has a hole-free proportional contact representations inside \(\mathcal{R}\) such that s occupies the entire left side of \(\mathcal{R}\), t occupies the entire right side of \(\mathcal{R}\), and no other vertices are on the outer-face of \(\mathcal{R}\).

Proof

We prove this by induction on the number of vertices. In the base case, G consists of edge (s,t) only, and we can easily create such a representation by splitting \(\mathcal{R}\) vertically so that the area to the left is w(s) and the area to the right is w(t).

So assume that G has at least three vertices. Define x 1,…,x k and graphs G 1,…,G k and \(G_{i}^{s}\), \(G_{i}^{t}\) as in the proof of Lemma 6. We proceed as follows:

  • Fix 0<ε<min{w(s),w(t)}.

  • For each i>0, let the weight of s in G i be \(\frac{1}{k}(w(s)-\varepsilon)\), i.e., split the weight of s among the subgraphs, and reserve a small amount of weight to be added later.

  • For each i>0, let the weight of t in G i be \(\frac{1}{k}(w(t)-\varepsilon)\).

  • Place k rectangles \(\mathcal{R}_{1},\dots,\mathcal{R}_{k}\) inside \(\mathcal{R}\) such that \(\mathcal{R}_{i}\) has area w(G i ) (with the above adjustments for s and t). No two of these rectangles touch each other or touch the boundary of \(\mathcal{R}\), but each of them spans almost the entire width of \(\mathcal{R}\), and we choose their height so that the area is correct. This is possible since w(G 1)+⋯+w(G k )=w(G)−2ε.

  • For each i>0, let the weight of x i in \(G_{i}^{s}\) and \(G_{i}^{t}\) be \(\frac{1}{2}w(x_{i})\) each.

  • Split each rectangle \(\mathcal{R}_{i}\) vertically such that area to the left is \(w(G_{i}^{s})\) and the area to the right is \(w(G_{i}^{t})\) (with the above adjustment for x i ).

  • By induction each \(G_{i}^{s}\) and \(G_{i}^{t}\) has a proportional contact representation that fits inside the rectangle reserved for these graphs. Furthermore, the two polygons of x i in these representations abut the dividing line of \(\mathcal{R}_{i}\).

  • Find a vertical line such that the area of \(\mathcal{R}-\bigcup \mathcal{R}_{i}\) to the left of it is ε.

  • Add this area to the left of the dividing line to s, and all the remaining area of \(\mathcal{R}-\bigcup\mathcal{R}_{i}\) to t.

Figure 8 illustrates the construction. One easily verifies that the areas of polygons are correct. To see that adjacencies are correct, note that only s, x i and t i are on the outside of \(\mathcal{R}_{i}\). Since G is maximal series-parallel, edges (s,t), (s,x i ) and (x i ,t) must exist, so filling the holes with s and t does not add unwanted adjacencies.

Fig. 8
figure 8

The hole-free construction for a series-parallel graph. k=3 in this example

Full size image

Similarly as in previous sections, the inductive argument can be turned into a recursive algorithm, and it can be implemented in linear time if we pre-compute the weights w(G 1),…,w(G k ) by splitting the graph into its smallest components first, and then computing the weights while combining components. Once these weights are computed, the time in each recursion is then proportional to the number of parallel components with terminals {s,t}, which is O(m)=O(n) total. □

We note here the complexity of the polygon of vertex v is O(deg(v)): this clearly holds in the base case, and is easily proved by induction since s and t receive O(k) additional corners. The example of \(K_{2,n}^{+}\) shows that a complexity of Ω(Δ) is required, where Δ denotes the maximum degree, so this is asymptotically optimal.

Theorem 5

O(Δ) sides are always sufficient and sometimes necessary for hole-free proportional contact representation of maximal series-parallel graphs.

6 Conclusion

We gave an algorithm for a proportional contact representation of a maximal planar graph with 10-sided rectilinear polygons, which improves on the previously known upper bound of 12.

We also described algorithms for special classes of maximal planar graphs that create representations with fewer sides. We achieve 8-sided rectilinear polygons for planar 3-trees, 4-sided polygons for maximal outer-planar graphs (or 6-sided polygons if the outerface is a rectangle), and 6-sided polygons for maximal series-parallel graphs if small holes are allowed. All these results achieve the smallest number of sides that is possible within this class of graphs.

All algorithms in this paper can be implemented in linear time, and require nothing more complicated than Schnyder realizers and other elementary planar graph manipulations. In contrast, the very recent improvement in the number of sides to 8 [2], the proof is non-constructive and requires numerical approximations to find the contact representation. Finding a constructive proof (and preferably linear-time algorithm) to construct 8-sided proportional contact representations of maximal planar graphs remains open.