Approximation Algorithms for Some Topological Invariants of Graphs

(1)

Timo Poranen

Approximation Algorithms for Some Topological Invariants of

Graphs

academic dissertation

To be presented, with the permission of the Faculty of Information Sciences of the University of Tampere, for public discussion in

the B1096 Auditorium of the University on October 22nd, 2004, at 12 noon.

department of computer sciences university of Tampere

A-2004-7 Tampere 2004

(2)

University of Tampere

Professor Jyrki Nummenmaa Department of Computer Sciences University of Tampere

Opponent: Professor Ville Lepp¨anen

Department of Information Technology University of Turku

Reviewers: Professor Robert Cimikowski Department of Computer Science Montana State University

Professor Tapio Elomaa Institute of Software Systems Tampere University of Technology

Department of Computer Sciences

FIN-33014 UNIVERSITY OF TAMPERE Finland

ISBN 951-44-6098-7 ISSN 1459-6903

Tampereen yliopistopaino Oy Tampere 2004

(3)

Abstract

Topological graph theory studies the embeddings of graphs on various surfaces and the properties of these embeddings. Topological properties of graphs have many applications in the fields of graph drawing, user interface design, circuit design, and resource location optimization.

This thesis studies approximation methods for the following NP-complete optimization problems: maximum planar subgraph, maximum outerplanar subgraph, and thickness of a graph. We also study the outerthickness problem which complexity status is not known. We compare the solution quality and computation times of a simulated annealing algorithm and several algorithms based on triangular cactus heuristic, including other heuristics taken from the literature, to approximately solve these problems.

Triangular cactus heuristic was the first non-trivial approximation algorithm for the maximum planar and outerplanar subgraph problems. We give a modified version of the triangular cactus heuristic that has at least equal performance ratio and asymptotic running time as the linear time version of the original algorithm. A large number of experiments show that the new algorithm achieves better approximations than the earlier methods.

We give two new theoretical results for the thickness and outerthickness of a graph. We prove a new upper bound for the thickness of complete tripartite graphs, and lower and upper bounds in the terms of the minimum and maximum degree of a graph for outerthickness. Also, the simulated annealing algorithm given in this work solves partially an open problem related to the thickness of the complete bipartite graphs. Our experiments show that the general formula also holds for some previously unknown cases.

(4)

(5)

Preface

The simulated annealing algorithm given in Chapter 4 for approximating thickness will appear inInformation Sciences [108]. Experiments reported in Chap- ter 8 are mainly taken from the article, but also some new approximations for large complete graphs are given in this work. The algorithm is also applied for outerthickness in Chapter 8. In the same article a new upper bound for the complete tripartite graphs was given. This result is discussed in Chapter 3 and experimented in Chapter 8.

The simulated annealing algorithm for the maximum planar subgraph problem appeared in International Journal of Computer Mathematics [109]. The algorithm is studied in Chapter 4 and experimental results are given in Chapter 6. The same algorithm is applied for approximating the maximum outerplanar subgraph problem in Chapter 7.

The new lower and upper bounds for outerthickness as the function of the minimum and maximum degree of a graph are given in Chapter 3. This result is based on an unpublished manuscript written with Erkki M¨akinen. The verification that the general formula holds for the previously unknown cases of the thickness of complete bipartite graphs, discussed in Section 8.7, is given in the same manuscript.

The genetic algorithm for determining the thickness of a graph, introduced in Chapter 4 and experimented in Chapter 8, is originally published together with Erkki M¨akinen and Petri Vuorenmaa [88].

(6)

(7)

Acknowledgements

I’m very grateful to my supervisors, professors Erkki M¨akinen and Jyrki Num- menmaa, for these years. Especially I thank Erkki’s supervising method, he has always given me constructive feedback of my writings. Jyrki was the man who made me interested in the graph theory.

I warmly thank all my colleagues and the old and new staff personnel of the Department of Computer Sciences for making the working environment enjoyable.

I’m grateful to Isto Aho, Jorma Laurikkala, Jouni Mykk¨anen, Timo Tossavai- nen, and Petri Vuorenmaa for scientific assistance and to Arto Viitanen for giving me many technical advises.

This work was funded by the Tampere Graduate School in Information Science and Engineering (TISE) and the University of Tampere, by awarding me a research stipend that gave me possibility to finish this thesis. Also the Academy of Finland (project 51528) has supported this work.

The greatest joy in my life during these years have been my wife Pirjo, and our children Niko, Toni, and Jenni. Thank you for your encouragement and support for this work!

Tampere, April 2004 Timo Poranen

(8)

(9)

Chapter 1 Introduction

Topological graph theory studies the embeddings of graphs on various surfaces and the properties of these embeddings [55]. Topological properties of graphs have many applications in the fields of graph drawing (information visualiza- tion) [38], VLSI circuit design [3], and resource location optimization [97].

An undirected, simple graph G (shortly a graph), denoted by G= (V, E), consists of a finite vertex set V and a set of undirected edges E ⊆ {(u, v) | u, v ∈V, u 6=v}. A graph is an abstract mathematical structure that models objects and connections between them. A graph can model any system involv- ing binary relations. Given a graphG= (V, E), a graphG⁰ = (V⁰, E⁰) is called a subgraph of Gif V⁰ ⊆V and E⁰ ⊆ {(u, v)|u∈V⁰, v ∈V⁰ and (u, v)∈E}.

A graph is usually visualized by representing each vertex through a point in the plane, and by representing each edge through a curve in the plane, connecting the points corresponding to the end vertices of the edge. Such a representation is called adrawing of the graph if no two vertices are represented by the same point, if the curve representing an edge does not include any other points representing a vertex (except its endpoints), and if two distinct edges have at most one common point. A drawing of a graph is plane if no two distinct edges intersect apart from their endpoints. A graph is planar if it admits a plane drawing, otherwise the graph is nonplanar. Such a drawing of a planar graph is called a plane embedding.

Two graphs are isomorphic if there exists a one-to-one correspondence between their vertex sets which preserves adjacency. An invariant of a graph G is a number associated with a property of Gwhich has the same value for any graph isomorphic toG. For example, a simple topological invariant of a graph is the number of vertices.

If a graph G⁰ = (V, E⁰) is a planar subgraph of G such that every graph G⁰⁰ obtained from G⁰ by adding an edge from E\E⁰ is nonplanar, then G⁰ is

(14)

called amaximal planar subgraphof G. Let G⁰ = (V, E⁰) be a maximal planar subgraph of G. If there is no planar subgraphG⁰⁰= (V, E⁰⁰) of Gwith |E⁰⁰|>

|E⁰|, then G⁰ is a maximum planar subgraph. A maximal planar subgraph is maximal in the sense that adding edges is not possible and the maximum planar subgraph is maximal with respect to the cardinality of its edge set. A graph isouterplanarif it admits a plane drawing where all its vertices surround the same region and no two distinct edges intersect, otherwise the graph is non-outerplanar. Maximal outerplanar subgraph and maximum outerplanar subgraph are defined in the similar way as the maximal and maximum planar subgraphs.

The thickness of a graph is the minimum number of planar subgraphs into which the graph can be decomposed. Similarly, the outerthickness of a graph is the minimum number of outerplanar subgraphs into which the graph can be decomposed.

Determining the maximum planar subgraph (MPS), maximum outerplanar subgraph (MOPS), and thickness of a given graph are known to be NP- complete (that is, there is no polynomial time algorithm for them, unless P=NP[51]). If a problem isNP-complete, we are unlikely to solve it exactly, but it might be possible to find near-optimal solutions in polynomial time using an approximation algorithm. The complexity status of determining the outerthickness of a graph is not known.

This work studies approximation methods and approximability results for determining MPS, MOPS, thickness, and outerthickness of a graph. We introduce several new algorithms that can be used to approximate these invariants.

Also, a comprehensive experimental study of the new algorithms against each other and against earlier heuristics algorithms from the literature is given. One of the new algorithms solves partially an open problem of unknown cases of the thickness of complete bipartite graphs. This work also contains two new theoretical results for thickness and outerthickness.

In Chapter 2, we give standard definitions and operations for graphs and introduce theoretical background for approximation algorithms, planarity and outerplanarity tests. We also introduce commonly used optimization methods, including guidelines to design experimental comparison of algorithms.

Chapter 3 recalls known theoretical results for the studied invariants. In this chapter, two new theoretical results for the thickness and outerthickness of a graph are given. The first result gives a new upper bound for the thickness of complete tripartite graphs, and the second result gives lower and upper bounds for outerthickness in the terms of minimum and maximum degree of a graph.

Further, an upper bound for outerthickness as a function of the number of

(15)

edges is conjectured.

Approximation algorithms for MPS, MOPS, thickness and outerthickness are presented in Chapter 4. We describe a new optimization method based on simulated annealing scheme to approximate MPS and MOPS. In addition, another simulated annealing algorithm for thickness and outerthickness is represented. Experiments given in Chapters 6, 7, and 8 show that the simulated annealing approach outperforms clearly the earlier heuristic algorithms.

The simulated annealing is quite time consuming approximation method and therefore Chapter 5 concentrates on methods that run in linear time for bounded degree graphs. We start with an algorithm based on triangular cactus heuristic, given by C˘alinescu et al. [26]. The algorithm was the first with non- trivial performance ratio for MPS and MOPS. Based on the triangular cactus approach, we give two new algorithms that have at least equal performance as the original algorithm and still run in linear time for bounded degree graphs.

The first algorithm approximates MPS and MOPS, the second algorithm gives approximations only for MPS. As shown in the experimental part of this work (Chapters 6, 7 and 8), these algorithms achieve clearly better approximations than the original triangular cactus heuristic. The exact performance ratio of the new algorithms is left open, but we state a conjecture that is supported by the experiments.

Chapters 6 and 7 describe an experimental comparison of the studied algorithms for MPS and MOPS, respectively. The test graph set [112] that is common with a few exceptions for both problems, contains 50 graphs.

The total number of the compared algorithms is 12 for MPS and 7 for MOPS. The experiments show that the new algorithms based on the triangular cactus heuristic (given in Chapter 5) and the simulated annealing algorithm (given in Chapter 4) produce the best known approximations for MPS and MOPS. No earlier experimental results for MOPS are presented in the literature.

Chapter 8 describes the experimental comparison of the algorithms for thickness and outerthickness. Thickness comparison contains approximation results for 12 algorithms and outerthickness comparison for 7 algorithms. The test graph set contains in total 63 graphs. Again, the experiments show that the simulated annealing is a very efficient method to approximate the thickness and outerthickness of a graph. The efficiency of simulated annealing is shown by solving some previously unknown cases of complete bipartite graphs. These results verify that the general formula holds for the solved cases. No earlier experimental results for outerthickness are presented in the literature.

The last chapter summarizes the results and lists the open problems that

(16)

have arisen from the theoretical and experimental parts of this work.

(17)

Chapter 2 Preliminaries

In this chapter we introduce basic definitions related to graphs and topological graph theory. We also define some important concepts related to algorithms.

After that, we give methods to recognize whether a graph is planar or outerplanar, and represent commonly used optimization methods. Finally, we describe guidelines to design experimental comparison of algorithms.

If some terms or notations related to graphs are unfamiliar, we recom- mend books written by Harary [60], Swamy and Thulasiraman [118] and Berge [14]. Moreover, Gross and Tucker [55] deal with topological graph theory and Liebers [84] surveys topics related to planarity and planarization of graphs.

Standard algorithm textbooks are Cormen et al. [36] and Knuth [77], while Even [44] concentrates only on graph algorithms. All algorithms in this work are given in similar format as in the book of Cormen et al. [36]. Garey and Johnson [51] give a formal approach for NP-complete problems and an introduction to optimization heuristics can be found in the book by Reeves [110].

2.1 Graphs

A graph is an abstract mathematical structure that models objects and connections between them. AgraphG, denoted byG= (V, E), consists of a finite set V of vertices and a set E ⊆ {(u, v) | u ∈ V, v ∈ V, u 6= v} of edges. If E = ∅, the graph is empty. In the literature vertices are sometimes called points or nodes and edges are lines or arcs. Given an edge e = (u, v), the verticesu and v are called the end vertices of e.

If the vertex pairs of the edge set are ordered, the graph is called directed and otherwise undirected. In undirected graphs, (u, v) = (v, u) for all edges, and in directed, (u, v)6= (v, u). We mainly consider undirected graphs. There- fore, if not stated otherwise, the graphs under consideration are undirected.

(18)

Two vertices u and v in V are said to be adjacent, if (u, v) ∈ E. The number of vertices|V|and edges|E|of a graph are often denoted byn andm, respectively. The complement G of a graph G has the same vertex set as G, but two vertices are adjacent inG if and only if they are not adjacent in G.

A path in a graph is a sequence of vertices v1, v2, v3, . . . , vk, where vertices v_i and v_i+1, 1≤i < k andk ≥2, are adjacent. A path is closed, ifv₁ =v_k and openotherwise. A path issimple, if all vertices of the path are distinct, except possibly the end vertices. If a path is simple and closed, it is a cycle. The length of a simple and open path is k−1, where k is the number of vertices in it. The length of a cycle is the number of vertices in it. A cycle of length n is denoted by Cn. A cycle of length three, C3, is a triangle. A triangle with vertices v₁, v₂, and v₃ is denoted by (v₁, v₂, v₃). A simple open path with n vertices is denoted byPn.

Given a graph G = (V, E), a graph G⁰ = (V⁰, E⁰) is called a subgraph of G if V⁰ ⊆ V and E⁰ ⊆ {(u, v) | u ∈ V⁰, v ∈ V⁰ and (u, v) ∈ E}. If not stated otherwise, we assume that V⁰ = V when we consider subgraphs. Let G = (V, E) be a graph and let E⁰ ⊆ E. Graph G⁰ = (V⁰, E⁰) is called an edge induced subgraph of G if V⁰ = {v |(u, v) ∈E⁰}. IfV⁰ ⊆V, then graph G⁰ = (V⁰, E⁰), where E⁰ = {(u, v) ∈ E | u ∈ V⁰ and v ∈ V⁰}, is a vertex induced subgraph of G. For a vertex induced subgraph G⁰ = (V \v, E⁰) of G= (V, E), we say that G⁰ is obtained fromG bydeleting orremoving v and that Gis obtained from G⁰ byinserting v.

If G1 = (V1, E1) and G2 = (V2, E2) are subgraphs of G = (V, E), then subgraph G⁰ = (V₁∪V₂, E₁ ∪E₂) of G is called the union of G₁ and G₂, and denoted byG1∪G2. IfV1 =V2 andE2 ={(u, v)}, then we say that edge (u, v) isinserted or added to G1.

A graph is connected, if there is a path between every pair of vertices, otherwise the graph is disconnected. A maximal connected subgraph of a graph is a component. A cut vertex of a graph is a vertex whose removal increases the number of components. If at least k vertices have to be deleted from the graph to make it disconnected, we say that the graph isk-connected.

Ak-connected componentis a maximalk-connected subgraph. A 2-connected component is also called biconnected.

A graph is a tree if it does not contain any cycles. A tree is a spanning tree, if there is a unique path between every pair of vertices. For a graph with n vertices, a spanning tree contains n−1 edges.

The degree of a vertex v is the number of adjacent vertices of v. The minimum degree of a graphG is denoted byδ(G) and the maximum degree is denoted by ∆(G), respectively. Ifr=δ(G) = ∆(G), Gis said to beregular of

(19)

2.1. GRAPHS degree r.

A graph G = (V, E) is bipartite, if the vertex set V can be partitioned into two subsets V₁ and V₂ such that for every edge (u, v) it holds that u∈V₁ and v ∈ V2. The join of graphs G1 = (V1, E1) and G2 = (V2, E2), denoted by G1+G2, is a graph with vertex set V1∪V2 and edge setE1∪E2∪ {(u, v)|u∈ V1 and v ∈V2}.

For n ≥1, the complete graph, denoted by Kn, consists of n vertices with all possible edges, that is, withn(n−1)/2 edges. Thecomplete bipartite graph, denoted by Kv1,v2, is the join of Kv1 and Kv2 and it has v1 +v2 vertices and v1v2 edges. Thecomplete k-partite graph, denoted by Kv1,v2,...,vk, is defined as the iterated join Kv1 +Kv2 +· · ·+Kvk. The complete k-partite graph has Pv_i vertices and P

i<jv_iv_j edges.

The product of graphs G1 = (V1, E1) and G2 = (V2, E2), denoted by G1× G2, is a graph with vertex set V1 × V2 and edge set defined as follows: let u= (u₁, u₂) and v = (v₁, v₂) belong to V₁×V₂. Vertices u and v are adjacent if u1 =v1 and u2 is adjacent with v2 inG2 or u2 =v2 and u1 is adjacent with v1 inG1. Am×n grid graph, wherem, n≥1 is product of simple open paths Pm and Pn and it containsmn vertices and 2mn−n−m edges.

Thehypercubeof ordern, denoted byQn, is defined recursively byQ1 =K2

and Qn = K2×Qn−1. Hypercubes are bipartite and Qn has 2ⁿ vertices and n2ⁿ⁻¹ edges. Hypercubes of order 1,2 and 3 determine a line, a square, and a cube, respectively.

A graph with n vertices is Hamiltonian, if there is a cycle Cn in G. If for two graphs G = (V, E) and G⁰ = (V, E⁰) it holds that |E| <|E⁰|, we say that G is sparser than G⁰ and that G⁰ is denser than G. When the graphs are compared, it is often said thatG is a sparse graph and G⁰ is a dense graph.

Two graphs are isomorphic, if between their vertex sets there exists a one- to-one correspondence which preserves adjacency. Lete= (u, v) be an edge of a graph. Edgeeissubdivided when we replaceeby adding a new vertexwand two new edges (u, w) and (w, v) to the graph. Two graphs are homeomorphic if both can be obtained from the same graph by a sequence of subdivisions.

For a graphG= (V, E) and an edge (u, v)∈E, the graphG⁰ obtained from Gby deleting (u, v), identifyingu withv, and removing all edges f ∈ {(u, x)| x∈ V, x 6=v,(u, x) ∈E, and (v, x)∈ E}, is said to have been obtained from G bycontracting the edge (u, v). A graph obtained from a subgraph of G by any number of edge contractions is said to be a minor of G.

A graph is usually visualized by representing each vertex through a point in the plane, and by representing each edge through a curve in the plane, connecting the adjacent points. Such a representation is called a drawing of

(20)

the graph if no two vertices are represented by the same point, if the curve representing an edge does not include any other points representing a vertex (except its endpoints), and if two distinct edges have at most one common point. A drawing of a graph is plane if no two distinct edges intersect. A graph is planar if it admits a plane drawing. Such a drawing of a planar graph is called a plane embedding. Regions in the plane that are defined by the drawing of a planar graph are called faces. Edges that form a region, are called theboundary edgesof the region, or shortly aboundary. The unbounded region is an outerface orexterior face and all the other regions are innerfaces.

Edges and vertices belonging to the outerface, are called exterior edges and exterior vertices, respectively. The other edges and vertices are interior edges andinterior vertices. If every face of a plane embedding of a graph is a triangle, the graph is calledtriangulated. A chord is an interior edge in which the end vertices are exterior.

A combinatorial embedding for a planar graph is a cyclic list of adjacent edges for each vertex such that if the edges are drawn in this order, a plane embedding is obtained. A graph may have many different combinatorial embeddings and some different combinatorial embeddings may yield similar draw- ings.

The famous Euler’s polyhedron formula (see [60], pp. 102-104 or [55], pp.

27-28) gives a connection for the number of faces, edges and vertices of a plane embedding. Since the result of Euler plays an important role in topological graph theory, we also give the proof.

Theorem 2.1. Let G be a connected planar graph with n vertices, m edges and f faces, then we have for the plane embedding of G that

n−m+f = 2.

Proof. The proof is by induction on the number of faces on the embedding.

For the base case, if the number of regions is one, that is, if f = 1, the graph must be a spanning tree. The formula holds, since for a connected tree we havem =n−1.

For the induction step, suppose that the equation holds when the number of regions is at most n, and suppose that for the graph G we havef =n+ 1.

Now some edge e lies in a cycle that is a boundary for two regions. Since the two regions are distinct, the subgraph G⁰ obtained from G by removing the edge e is connected. Denote the number of vertices, faces and edges of G⁰ by n⁰, f⁰ and m⁰. Since n⁰ = n, m⁰ = m−1 and f⁰ = f −1, it follows that n−m+f = 2.

(21)

2.1. GRAPHS The right side of the equation is theEuler characteristic of the surface. For the plane and sphere the Euler characteristic is 2. For the usage of the Euler’s polyhedron formula for the other surfaces, see [55] and the references given there.

Instead of searching graph’s plane embedding, for example, by paper and pencil, another way to characterize planarity is to recognize subgraphs that violate planarity. The following result is due to Kuratowski.

Theorem 2.2 ([79] (See also [60], pp. 108–112.)). A graph is planar if and only if it has no subgraph homeomorphic to K₅ or K_3,3.

See Figure 2.1 for an illustration of K5 and K3,3.

Figure 2.1: Basic nonplanar graphsK5 and K3,3.

If a graph G⁰ = (V, E⁰) is a planar subgraph of G such that every graph G⁰⁰ obtained from G⁰ by adding an edge from E \E⁰ is nonplanar, then G⁰ is called a maximal planar subgraph of G. Let G⁰ = (V, E⁰) be a maximal planar subgraph of G. If there is no planar subgraph G⁰⁰ = (V, E⁰⁰) of G with |E⁰⁰| >|E⁰|, then G⁰ is a maximum planar subgraph. A maximal planar subgraph is maximal in the sense that adding edges is not possible and the maximum planar subgraph is maximal with respect to the cardinality of its edge set.

Figure 2.2 [84] illustrates the concepts of a planar subgraph, a maximal planar subgraph and a maximum planar subgraph of a nonplanar graph. Graph G1 is a planar subgraph of G. G1 is is not a maximal planar subgraph: edge (1,5) can be added to G1 without violating planarity. The result is G2 which is a maximal planar subgraph. Another maximal planar subgraph of G is G3

which is also a maximum planar subgraph.

A planar graph is outerplanar if it admits a plane drawing where all its vertices lie on the outerface and no two distinct edges intersect, otherwise the graph is non-outerplanar. Maximal outerplanar subgraph and maximum outerplanar subgraphare defined in the similar way as the maximal and maximum planar subgraphs.

(22)

!! ""## $$%% &&'' (())

**++ ,,-- ..// 0011 2233 4455 6677 8899 ::;; <<== >>??

@@AA BBCC DDEE

FFGG HHII JJKK LLMM

NON NON NON NON NON

POP POP POP POP POP

QOQ QOQ QOQ QOQ QOQ

ROR ROR ROR ROR ROR

SSSSTTTT

UUUUVVVV

WOWOW WOWOW WOWOW WOWOW WOWOW WOWOW WOWOW WOWOW WOWOW

XOXOX XOXOX XOXOX XOXOX XOXOX XOXOX XOXOX XOXOX XOXOX

YOY YOY YOY YOY YOY

ZOZ ZOZ ZOZ ZOZ ZOZ

[O[

\O\

]]]]^^^^

____````

aOaOa aOaOa aOaOa aOaOa aOaOa aOaOa aOaOa aOaOa aOaOa

bObOb bObOb bObOb bObOb bObOb bObOb bObOb bObOb bObOb

cOc cOc cOc cOc cOc

dOd dOd dOd dOd dOd

eOe eOe eOe eOe eOe

fOf fOf fOf fOf fOf

gggghhhh

iiiijjjj

kOk kOk kOk kOk kOk

lOl lOl lOl lOl lOl

mOm mOm mOm mOm mOm

nOn nOn nOn nOn nOn

oooopppp

qqqqrrrr

sOsOs sOsOs sOsOs sOsOs sOsOs sOsOs sOsOs sOsOs sOsOs

tOtOt tOtOt tOtOt tOtOt tOtOt tOtOt tOtOt tOtOt tOtOt

uuuuuuuuuvvvvvvvvv

wOwOw wOwOw wOwOw wOwOw wOwOw wOwOw wOwOw wOwOw wOwOw

xOxOx xOxOx xOxOx xOxOx xOxOx xOxOx xOxOx xOxOx xOxOx

6

3

1 5

7 6

3

1 5

7 6

3

1 5

7

G

₃

G

₁

6

3

1 5

7

G G

₂

2 4 2 4 2 4 2 4

Figure 2.2: An example illustrating the concepts of planar subgraph (G1), maximal planar subgraph (G₂) and maximum planar subgraph (G₃) of a nonplanar graph (G).

Outerplanar graphs have a similar characterization as planar graphs.

Theorem 2.3 ([28]). A graph is outerplanar if and only if it has no subgraph homeomorphic to K4 or K2,3.

Figure 2.3 shows graphs K4 and K2,3 which violate outerplanarity.

yyzz

{{|| }}~~

Figure 2.3: Basic non-outerplanar graphs K4 and K2,3.

A maximal planar graph is a planar graph with the property that the addition of any edge results in a nonplanar graph. A maximal outerplanar graph (mop) is an outerplanar graph with the property that the addition of any edge results in a non-outerplanar graph.

The number of triangular faces of a maximal planar graph can be derived from Theorem 2.1.

Theorem 2.4. Given a maximal planar graph with n vertices and m edges, the graph contains 2n−4 triangular faces.

Next we give a useful characterization for mops [16, 13] having at least three vertices. The definition is needed later in this work.

(23)

2.2. ALGORITHMS AND COMPUTATIONAL COMPLEXITY Definition 2.5. Mops having at least three vertices can be defined recursively as follows:

1. K3 is a mop.

2. If G is a mop which is embedded in the plane so that every vertex lie on the outer face, and G⁰ is obtained by joining a new vertex to two vertices of an edge on the outer face of G, then G⁰ is a mop.

3. GraphH is a mop if and only if there is one application of statement (1) and a finite sequence of applications of statement (2) to obtain H.

There is also a straight connection between outerplanar graphs and planar graphs. The theorem below is mentioned by Wiegers [132], but probably it is older.

Theorem 2.6. A graph G is outerplanar if and only if G+K₁ is planar.

2.2 Algorithms and computational complexity

An algorithm consists of a finite set of well defined instructions which gives a sequence of operations for solving a specific problem [77]. An algorithm has usually at least one input and at least one output. An algorithm transforms the input into the output by performing a sequence of computational steps. An algorithm is deterministic if for a fixed input, the algorithm produces always the same output. Otherwise it is non-deterministic. A randomized algorithm makes random choices during its execution.

Algorithms 2.1 (DFS) and 2.2 (Search) illustrate the concept. These algorithms perform depth-first search for the input graph, that is, all vertices and edges are explored. The name of the algorithm is given first (DFS) and the input is given in the parenthesis (G = (V, E)). Standard ways to give an encoding for a graph are adjacency lists and adjacency matrices. In the adjacency list there is an entry, a list, for each vertex, where the adjacent vertices are given. The adjacency matrix for a graphG= (V, E) is a |V| × |V| matrix where row i shows the adjacent vertices for the ith vertex as follows.

The entry i, j is 1, if there is an edge between vertices i and j, otherwise the entry is 0. The adjacency matrix needs space proportional to |V|², while adjacency list needs space proportional to |E|.

The description of DFSis finite: its instructions are given as a finite list of numbered steps. In general, one step may contain more than one instruction.

(24)

DFS(G= (V, E)) 1 T ← ∅;

2 mark all vertices in V unvisited

3 while there is an unvisited vertex u inV; 4 do Search(u);

5 return T;

Algorithm 2.1: DFS.

Search(u)

1 marku visited;

2 for each v that is adjacent to u 3 do if v is not visited 4 T ←T ∪ {(u, v)};

5 Search(v);

Algorithm 2.2: Search.

Algorithm search(u)is a subalgorithm of DFS, since if the condition statement in Step 3 is true, DFScalls Search. When we refer later in this work toDFS, we assume that alsoSearch belongs to the description of DFS.

Depth-first search has many applications in the field of graph algorithms, since it can be used as a skeleton for other algorithms. For example, we can construct a spanning tree for a given graph. Set T, where the edges of the spanning tree will be stored, is initialized as empty in Step 1 of DFS. If we arrive during the dfs-traversal from a visited vertex u to an unvisited vertex v in Search, we add (u, v) to T (Step 4). These edges are called the tree- edges of the graph. The other edges are the back-edges. If the input graph is connected, then in the end of DFSedges inT form a spanning tree. DFScan produce different spanning trees depending on the order in which the edges and vertices are searched. If the tree-edges found in a dfs-traversal are directed in the natural way, we get a dfs-tree for the graph. T is returned in the last step of the algorithm.

DFScan also be used to check if a graph is connected: it is enough to count how many times Search is called in Step 4 of DFS. If there are zero calls, the input graph is empty, otherwise the graph contains as many connected

(25)

2.2. ALGORITHMS AND COMPUTATIONAL COMPLEXITY components as there are calls for Search. DFS can also be used to find biconnected components of a graph [124].

Other applications of DFS in this work are planarity testing algorithms studied in the next section, a heuristic to make the graph connected in Chap- ter 5, and a spanning tree heuristic for approximating different topological invariants discussed in Chapter 4.

To classify different algorithms, a common way is to compare their running times. The running time can be “wall-clock” time, when we start the clock at the same time as the algorithm begins and stop the clock when the algorithm halts. The wall-clock time depends highly on the implementation of the algorithm and on the efficiency of the execution platform. A platform independent approach is to study the number of base operations of the algorithm as the function of the input size. This can be done using asymptotic notations. Con- sider functions f : N → R⁺ and g : N → R⁺. Function f is O(g), if there exists positive constants cand n0 such that f(n)≤cg(n), when n≥n0.

If the number of base operations, f(n), for all inputs of sizen is O(g(n)), we say that the running time of the algorithm is O(g(n)). If g(n) = n^k for some positive constant k, we say that the algorithm is polynomial. Especially wheng(n) is a polynomial function of the first order, we say that the algorithm is linear.

As an example, consider again DFS. It takes a graph as input and then it chooses a vertex from where it starts exploring the other vertices and edges.

Finally, all vertices and edges of the graph are explored. Since DFS gets a graph as input, it is reasonable to study the running time as a function of numbers of edges and vertices. We may assume that the input graph is represented by its adjacency list. We count how many assignments and searches for the adjacency lists are made during the execution of DFSfor a graph with n vertices and m edges. Step 1 is performed once and each of Steps 2, 3 and 4 are performed at most n times. Algorithm Search is called in total n times in Step 4 of DFSand in Step 5 of Search. The adjacency lists of each vertex are explored once in Step 2 of Search, so this takes time proportional to m.

By adding these all together, we get an O(m+n) time algorithm.

The class of problems that are solvable in polynomial time is denoted byP. If the time complexity of the algorithm cannot be bounded by any polynomial, we say that the algorithm is exponential. Some problems are such that we do not know, if they have a deterministic polynomial time algorithm. For these problems it might be possible to find the solution non-deterministically in polynomial time: we can guess the solution and verify the correctness of the solution in polynomial time. The class of problems that have a non-

(26)

deterministic polynomial time algorithm is denoted by NP. It is obvious that P⊆ NP, but whether the inclusion is proper or not, is one of the main open questions in the theoretical computer science.

One of the reasons why most theoreticians believe that P 6= NP, is the existence of NP-complete problems. This class has the property that if any of its problems can be solved in polynomial time, then every problem inNPcan be solved in polynomial time. The reason behind this is that all problems inNPare polynomially transformable to any NP-complete problem. Since no polynomial time algorithm for anyNP-complete problem is known, this gives a good evidence for the intractability of the NP-complete problems.

Many computational problems, for example, determining the maximum planar or outerplanar subgraph of a graph, areNP-complete. To find optimal solution may require exponential time in the function of the input size: the whole set of possible solutions have to be checked before we can be sure that the optimal solution is found. This kind of method is calledexhaustive search.

Since the running time of the exhaustive search can be very high even for small problem instances, we do not usually require to solve the problem optimally in practical situation. It is enough to find solutions that are close to optima.

Algorithms that return always some solution, but not necessarily optimal, are called approximation algorithms. Fast approximation algorithms can handle much larger input instances than the algorithms based on exhaustive search.

One way to compare approximation algorithms is to study the ratio of the worst possible solution that the approximation algorithm can return and the optimal solution. This is called the performance ratio of the algorithm. Let G be a problem instance, A(G) ≥ 0 the solution obtained by approximation algorithm A and OP T(G) ≥ 0 the optimal solution for input G. Next we define the performance ratio for maximization problems.

Definition 2.7. The performance ratio R_A(P)of an approximation algorithm A for a maximization problem P is the minimum ratio of obtained solutions to the cost of optimal solution:

RA=

( min_{OP T}^A(G)_(G) , if OP T(G)6= 0 1 , if OP T(G) = 0.

The performance ratio for minimization problems is similar, but now the optimal solution is the denominator and the worst solution is the numerator.

Definition 2.8. The performance ratio RA(P)of an approximation algorithm A for a minimization problem P is the maximum ratio of obtained solutions to the cost of optimal solution:

(27)

2.3. TESTING PLANARITY AND OUTERPLANARITY

RA=

( max_{OP T}^A(G)_(G) ,if A(G)6= 0 1 ,if A(G) = 0.

2.3 Testing planarity and outerplanarity

One way to test graph’s planarity is to apply Theorem 2.2 that gives a struc- tural property of nonplanar graphs. By searching directly subgraphs homeomorphic to K5 and K3,3 from the graph we obtain an O(n⁶) algorithm [63].

Although the running time is polynomial, it is too slow for practical applications.

The other approach is to construct the plane embedding by an algorithm.

We know that the graph is planar, if the construction succeeds and otherwise we can recognize forbidden subgraphs that violate planarity. The first such planarity testing algorithm was described by Auslander and Parter [8], cor- rectly formulated by Goldstein [54] and implemented to run inO(n³) time by Shirey [116]. Finally Hopcroft and Tarjan gave a linear time implementation for the algorithm [63]. Clearly any planarity testing algorithm needs at least linear time in the number of vertices and edges of the graph, so this algorithm is optimal up to a constant factor.

Next we introduce the basic ideas behind this path-addition approach to test planarity. We show, following [38], how cubic running time can be achieved. Linear time implementation is quite involved, a detailed description can be found from [111, pp. 364-385] and [93, 92]. The algorithm is based on divide-and-conquer approach. The following property of planar graphs is elementary and trivial. It shows a natural way to divide the problem into smaller subproblems.

Lemma 2.9. A graph is planar if and only if all its biconnected components are planar.

By Lemma 2.9, we may assume without loss of generality, that the graphG, whose planarity will be tested, is biconnected (if the input graph is not biconnected, we can test the planarity of every biconnected component separately).

Next we divide Ginto smaller subgraphs, calledpieces. LetC be an arbitrary cycle of G. Now the edges not inC are partitioned into classesE₁, E₂, . . . , E_p as follows: two edges are in the same class if there is a path between them that does not contain any vertices of C. Each edge class Ei induces a subgraph of G, called piece Pi. The vertices of a piece Pi that belong to C are called attachments of P. We may assume that the number of pieces is greater than

(28)

or equal to two. If there are no pieces at all, thenGis a cycle and therefore it is planar. If there is only one piece, the graph is planar if and only if the piece is planar (if a piece is planar, it can be embedded inside or outside of C).

There are two types of pieces with respect to C:

1. an edge whose endpoints belong to C, or

2. a connected subgraph with at least one vertex not in C.

It is obvious that the whole piece should be drawn inside or outside of C. The next task is to check that is it possible to divide the pieces into two sets such that the first set is embedded on the outside of C and the second set inside of C. To check if there are embeddable pieces, we construct a so called interlacement graph. Two pieces interlace, if they cannot be drawn on the same side ofC without violating planarity. This can be checked using the attachments and the types of the pieces. The interlacement graphI of pieces is the graph whose vertices are the pieces of G and there is an edge between the vertices if the corresponding pieces interlace. Now, ifI is bipartite, pieces can be embedded inside and outside ofC, otherwise the planarity is violated.

The described procedure is applied recursively to all pieces. If all pieces are planar and they can be embedded inside and outside of the cycle, we recognize that the graph is planar. This leads to anO(n³) time algorithm. The algorithm of Hopcroft and Tarjan [63] is based on using DFS to find the cycle and to recognize the pieces. The algorithm tries to embed pieces inside and outside of the cycle in a good order and using a complicated stack data structure to achieve the linearity.

The second planarity testing paradigm isvertex additionapproach. Rather than adding an edge or a path, the algorithm starts from a single vertex, and the remaining vertices are considered in some predefined order. A vertex with its adjacent edges to already embedded vertices are added to the planar subgraph. This process is continued until a plane embedding is achieved for the graph, or an edge that violates planarity is found. First vertex addition algorithm was given by Lempel et al. [82]. The algorithm was based on calculating first a suitable numbering for the vertices, and then adding vertices in this order. The authors did not give implementation or complexity analysis for the algorithm. Later Even and Tarjan [45] showed that the suitable numbering can be found in linear time and finally a linear time implementation was given by Booth and Lueker [20]. The algorithm uses a data structure calledP Q-trees.

Later Shih and Hsu [115] gave a new simpler linear time planarity testing algorithm. The algorithm uses a PC-tree data structure [66] and it is based on vertex addition approach. The second new linear time planarity testing

(29)

2.3. TESTING PLANARITY AND OUTERPLANARITY algorithm is given by Boyer and Myrwold [23]. This algorithm is also based on vertex addition approach and it is similar to that of Booth and Lueker [20].

For the implementation details concerning the algorithms of Shih and Shu, see [65] and for the algorithm of Boyer and Myrwold, see [22].

A dynamic planarity testing algorithm [50] maintains a data structure to represent a planar graph G = (V, E) in such a way that the algorithm can answer to the following question

1. For two vertices u and v inV with (u, v)6∈E, is (V, E∪(u, v)) planar?

and make the following updates to the data structure:

2. For two vertices u and v in V with (u, v) 6∈ E, add (u, v) to E (in the case of positive answer for the question 1).

3. Delete an edge efrom E.

4. Add a new vertex to V.

5. Delete a vertex from V with all its adjacent edges.

An algorithm is called semi-dynamic, if it supports only insertions or dele- tions, but not both. Dynamic planarity testing algorithms can be used to search maximal planar subgraphs of a given graph, and these methods are examined in Section 4.1.

Next we study methods to test the outerplanarity of a given graph. Theo- rem 2.6 gives a direct way to apply any planarity testing algorithm to recognize also outerplanar graphs. Since it takes only linear time to add one vertex v to an input graph G = (V, E) and to add |V| edges to make v adjacent with the vertices of G, it takes asymptotically the same time to apply a planarity testing algorithm to test outerplanarity. Since planarity testing algorithms are quite involved, there exists also pure outerplanarity testing algorithms.

In the end of 1970’s, three outerplanarity testing algorithms were given.

Brehaut [24] gave a linear time algorithm that was based on the same idea as the Hopcroft-Tarjan planarity testing algorithm, without any need for complicated data structures. Also, an algorithm by Syslo and Iri [121] was based on a similar approach (see also an article by Syslo [120] for characterization, testing, coding, and counting of outerplanar graphs). The third algorithm was given by Mitchell [96], and it was designed to recognize maximal outerplanar subgraphs. The approach was simpler than in the previous two algorithms:

for a biconnected graph withn vertices, the algorithm deletes n−2 vertices of

(30)

degree two from the graph. If the deletion of a degree two vertex was not possible or if an occurrence of an illegal element was added in an edge list during the execution, the graph was recognized to be non-maximal outerplanar. The algorithm recognizes also outerplanar graphs with minor modifications.

The previous outerplanarity testing algorithms required that the graph should be first divided into biconnected components. Wiegers [132] gave an algorithm that is based on deleting successively vertices of degree less than or equal to two from the input graph, without a need to divide the graph into biconnected components.

2.4 Combinatorial optimization

In this section we introduce commonly used optimization paradigms for com- putationally hard problems. The discussed methods include local search, simulated annealing, genetic algorithms and branch-and-bound heuristic. These methods produce only approximations if the running time is limited.

2.4.1 Local search

The basic idea behind all local search algorithms is to choose aninitial solution, denoted by s0, and then trying to improve the quality of this solution [110].

The improvements are done by choosing another solution that belongs to the neighborhood, denoted by N(s0), of the current solution. The neighborhood of a solution is a set of other solutions that are close of the current solution (where the definition of “close” depends on the problem in question). This new solution is accepted to be the new current solution, if some requirements are fulfilled. Acceptance criterion could be that the new solution always im- proves the current solution (hillclimbing) or that it does not make the current solution too much worse (simulated annealing), or the whole neighborhood is searched and the best neighbor solution is chosen. All these algorithms have a stopping criterion (termination condition), that might be the number of iter- ation steps, or notifying that there are no possibilities to improve the current solution anymore. See Algorithm 2.3 for the general structure of a local search algorithm.

There are several problem dependent parameters to be decided when the algorithm is implemented: how the set of possible solutions is represented, what is a good definition for the neighborhood structure, what is the stopping criterion, and how the initial solution is constructed.

(31)

2.4. COMBINATORIAL OPTIMIZATION

Local-Search

1 select an initial solution s0; 2 while not termination condition

3 do randomly select a solution s∈N(s0) 4 if s is acceptable

5 then s0 ←s;

6 return s₀;

Algorithm 2.3: Basic structure of a local search algorithm.

2.4.2 Simulated annealing

Simulated annealing (SA) algorithm imitates the cooling process of material in a heat bath. SA was originally proposed by Kirkpatrick et al. [75] based on some ideas given by Metropolis et al. [94].

The search begins with initial temperature t0 and ends when temperature is decreased to frozen temperature tl, where 0 ≤ tl ≤ t0. The equilibrium detection rate r tells when an equilibrium state is achieved, and temperature is decreased geometrically by multiplying current temperature by the cooling ratioα, where 0< α <1. To determine good parameters for a given problem is often a hard task, and it needs experimental analysis. There are also adaptive techniques for SA[127].

The temperature of the simulated annealing algorithm gives the probability of choosing solutions that makes the current solution worse. If there are many bad solutions in a neighborhood of a “better” solution, and these bad solutions are accepted too often, the algorithm does not converge to a good solution.

If the good solutions are rare and the bad solutions appear very often, the temperature should be low enough to ensure that the bad solutions are not accepted too often.

See Algorithm 2.4 for the general structure of the simulated annealing for a maximization problem. In Step 6, “Cost” denotes the goodness of the solution, and it is depended on the problem in question.

Often it is possible to improve the solution quality and to decrease the needed computation time of SAby finding a better initial solution than a randomly generated solution [5, 69, 110]. For more details concerning simulated annealing algorithms, see [1, 110, 127] and the references given there.

(32)

SA

1 select a cooling ratio α and an initial temperature t0;

select a frozen temperaturetl and an equilibrium detection rate r;

select an initial solution s0; set t←t0 and e ←0;

2 while t≥tl

3 do whilee ≤r

4 doe←e+ 1;

5 randomly select a solution s∈N(s0);

6 δ ←Cost(s)−Cost(s0);

7 generate a random integer i, 0 ≤i≤1;

8 if i≤e^−δ/t

9 then s0 ←s;

10 t ←αt;

11 e ←0;

12 return s0;

Algorithm 2.4: Basic structure of a simulated annealing algorithm.

2.4.3 Genetic algorithms

The general principle underlying genetic algorithms is that of maintaining and improving a set of possible solutions, often called population, instead of only one solution as in SA. The population undergoes an evolutionary process which imitates the natural biological evolution. In each generation better solutions candidates have a greater change to reproduce, while worse solutions are more likely to die and to be replaced by new solutions. To distinguish between “good” and “bad” solutions there is a need to define an evaluation function that maps each solution to a real number.

The general structure of a genetic algorithm is given in Algorithm 2.5 (GA).

The basic operations in recombination are the mutation and crossover operations. Mutation is a unary operation which increases the variability of the population by making pointwise changes in the representation of the solutions.

Usually crossover combines the features of the two parents to form two new solutions by swapping corresponding segments of the parents’ representations.

See Mitchell [95] for further details concerning genetic algorithms.

(33)

2.4. COMBINATORIAL OPTIMIZATION

GA 1 t ←0;

2 create the initial population P(0);

3 evaluate the initial population;

4 while not termination condition 5 do t←t+ 1;

6 select solution candidates to be reproduced;

recombine (i.e. apply genetic operations to create the new population P(t));

7 evaluate P(t);

8 return the best solution fromP(t);

Algorithm 2.5: Basic structure of a genetic algorithm.

2.4.4 Branch-and-bound

One method to solve a discrete and finite optimization problem is to generate all possible solutions and then choose the best one of them. For NP-complete problems this exhaustive search method fails since the number of solutions is exponential in the size of the input. For example, given a graph G = (V, E), there exists 2^|E| different subgraphs containing all|V|vertices. If the problem in question asks a subgraph of the given graph with some specific property, it is possible that all subgraphs need to be checked before the right one is found.

Only small instances can be solved in this way.

Branch-and-bound is a method that can be used in the exhaustive search by recognizing partial solutions that cannot lead to an optimal solution. For example, suppose that we know that the optimal solution for a maximization problem is at least k (we have found a solution with cost k). If during the generation of the other solution candidates we recognize that the current solution cannot be augmented to any solution with cost≥k, we can stop gen- erating these solution candidates and continue searching from more promising solutions.

The efficiency of the branch-and-bound techniques depends highly on the problem in question and the order in which the solution candidates are found.

If the lower bound for the optimal solution is bad, there are little possibilities to reject any solutions. The worst case running time of branch-and-bound is still exponential, but often it decreases the computation time remarkably.

(34)

2.5 Experimental algorithmics

Analysis of algorithms concentrates on determining the theoretical properties of algorithms, for example, what is the running time of an algorithm, how much space an algorithm needs in the worst case, and if an algorithm is an approximation algorithm, what is its performance ratio.

In practice, the theoretical analysis of an algorithm is not always enough.

The algorithm might be so complicated that it is almost impossible to imple- ment it to run within the claimed asymptotic time and space bounds. The worst case performance ratio of the algorithm can be poor, but for all reasonable inputs the solutions are of good quality. The constant factor of the asymptotic running time could be so high that another algorithm with a polynomially higher running time can be faster for small inputs.

Yet another reason using non-theoretic approaches to study the properties of an algorithm could be the hardness of the theoretical analysis. For example, if the performance ratio of the algorithm is not known, the only way to test the efficiency of the algorithm is experimental analysis. We can run the algorithm for a number of inputs (test instances) and try to draw some conclusion about the outputs. For an algorithm with an unknown performance ratio it is possible to use the experimental analysis to get a good guess on the possible performance ratio. In the best case, the experimental analysis may lead to new theoretical results. This may also help to recognize parts of the algorithm which can be improved to make it more efficient.

In general, the experimental analysis of algorithms can be used to compare the running times and solution qualities of different algorithms. There are several guidelines to perform reliable comparison of algorithms, next we recall some suggestions given by Johnson [68], Moret [98], McGeoch [91], and Moret and Shapiro [99].

Define the goal of the study clearly. If the aim of the research is not clear enough in the beginning of the work, the study may go to totally wrong direc- tions. The researcher should be familiar with his research area, mainly on the earlier results. When the goal of the study is clearly defined, it is easier to start asking right question to design the experimental setup well. This decreases the danger on devoting too much computation time to wrong questions. During the experimentation process, there might appear new subgoals, or the old goal may be changed to a better one.

Use a reasonably large number of well chosen test instances. When the goal is clear, it is easier to construct a testbed that can be used to find differences between the algorithms and can tie the experiments with the real world. The

(35)

2.5. EXPERIMENTAL ALGORITHMICS testbed should contain instances from the real world applications and (randomly) generated instances. The generated instances can be used to test some specific properties of the algorithms, mainly their weaknesses and strengths.

Often a testbed includes test instances with the known optima, and random instances whose optima is not known. Furthermore, the earlier testbeds should be taken into account to tie the experiments to the literature. At least some test instances should be large enough to support justified conclusions about the (asymptotic) running time of the algorithms.

Draw justified conclusions. Reporting just the solutions of the experimented algorithms is not enough. There should be drawn conclusions from the data that are related to the goal of the study. For example, can we sort the algorithms by their running time difference or by their solution quality?

Is it possible to recognize test instances which are good for an algorithm, but bad for another algorithm? When the differences of the algorithms are not clear enough, there is often a need to apply statistical methods to justify the conclusions.

Ensure reproducibility and comparability of the experiments. The reported measures of the algorithms should be comparable with the earlier results, and it should also be possible to apply the results in the forthcoming experiments.

Since the test platform affects highly on the running time of the algorithms, the exact description about the used computer should be given. All the test instances, source codes of the algorithms and instance generators should be available to the public. This ensures that other researchers can reproduce all experiments.

(36)

(37)

Chapter 3 Topological Invariants

Aninvariant of a graphGis a number associated with a property of Ghaving the same value for any graph isomorphic toG. Topological invariants describe a graph’s embeddability on different surfaces. In what follows, the used surface is the plane.

In this chapter we define the following four topological invariants: maximum planar subgraph, maximum outerplanar subgraph, thickness, and outerthickness. If a graph is not (outer)planar, these invariants give an approximation how far away from (outer)planarity the graph is. We recapitulate known results and give some new results for the thickness and outerthickness of a graph.

3.1 Maximum planar subgraph

The maximum planar subgraph problem (MPS) is defined as follows.

Definition 3.1. MPS: given a graph G = (V, E), how many edges are there in a maximum planar subgraph G⁰ of G?

MPS is one of the most studied topological invariants that can be found in the literature. The origin of MPS lies in so called facility layout problem, where different facilities are assigned on a plane in order to minimize distances and flows between them [97, 61]. MPS also plays an important role in graph drawing [70, 123], since a large planar subgraph can be used to obtain layouts fulfilling many aesthetic criteria [38].

Determining MPS is actually the same as determining the skewness of a graph G, i.e., the minimum number of edges whose removal leads to a planar subgraph. If we can determine a subgraph G⁰⁰ = (V, E⁰⁰), whose extraction leads to a maximum planar subgraph G⁰ = (V, E⁰), we know that skewness is

Approximation Algorithms for Some Topological Invariants of Graphs

Timo Poranen