In this thesis we prove two main results. The Triangle Conjecture asserts that the convex hull of any optimal rectilinear drawing of <em>K_n</em> must be a triangle (for <em>n</em> &ge; 3). We prove that, for the larger class of pseudolinear drawings, the outer face must be a triangle. The other main result is the next step toward Guy's Conjecture that the crossing number of <em>K_n</em> is $(1/4)[n/2][(n-1)/2][(n-2)/2][(n-3)/2]$. We show that the conjecture is true for <em>n</em> = 11,12; previously the conjecture was known to be true for <em>n</em> &le; 10. We also prove several minor results.

In this thesis we prove two main results. The Triangle Conjecture asserts that the convex hull of any optimal rectilinear drawing of <em>K_n</em> must be a triangle (for <em>n</em> &ge; 3). We prove that, for the larger class of pseudolinear drawings, the outer face must be a triangle. The other main result is the next step toward Guy's Conjecture that the crossing number of <em>K_n</em> is $(1/4)[n/2][(n-1)/2][(n-2)/2][(n-3)/2]$. We show that the conjecture is true for <em>n</em> = 11,12; previously the conjecture was known to be true for <em>n</em> &le; 10. We also prove several minor results.

The crossing number of a graph is the minimum number of pairwise crossings of edges among all planar drawings of the graph. A graph G is k-crossing critical if it has crossing number k and any proper subgraph of G has a crossing number less than k. The set of 1-crossing critical graphs is is determined by Kuratowski’s Theorem to be {K5, K3,3}. Work has been done to approach the problem of classifying all 2-crossing critical graphs. The graph V2n is a cycle on 2n vertices with n intersecting chords. The only remaining graphs to find in the classification of 2-crossing critical graphs are those that are 3-connected with a V8 minor but no V10 minor. This paper seeks to fill some of this gap by defining and completely describing a class of graphs called fully covered. In addition, we examine other ways in which graphs may be 2-crossing critical. This discussion classifies all known examples of 3-connected, 2-crossing critical graphs with a V8 minor but no V10 minor.

The crossing number of a graph is the minimum number of pairwise crossings of edges among all planar drawings of the graph. A graph G is k-crossing critical if it has crossing number k and any proper subgraph of G has a crossing number less than k. The set of 1-crossing critical graphs is is determined by Kuratowski’s Theorem to be {K5, K3,3}. Work has been done to approach the problem of classifying all 2-crossing critical graphs. The graph V2n is a cycle on 2n vertices with n intersecting chords. The only remaining graphs to find in the classification of 2-crossing critical graphs are those that are 3-connected with a V8 minor but no V10 minor. This paper seeks to fill some of this gap by defining and completely describing a class of graphs called fully covered. In addition, we examine other ways in which graphs may be 2-crossing critical. This discussion classifies all known examples of 3-connected, 2-crossing critical graphs with a V8 minor but no V10 minor.

The crossing number of a graph 𝐺 is the minimum number of crossings in any drawing of 𝐺 in the plane. The rectilinear crossing number of 𝐺 is the minimum number of crossings in any straight-line drawing of 𝐺. The Fáry-Wagner theorem states that planar graphs have rectilinear crossing number zero. By Wagner’s theorem, that is equivalent to stating that every graph that excludes 𝐾₅ and 𝐾₃,₃ as minors has rectilinear crossing number 0. We are interested in discovering other proper minor-closed families of graphs which admit strong upper bounds on their rectilinear crossing numbers. Unfortunately, it is known that the crossing number of 𝐾₃,ₙ with 𝑛 ≥ 1, which excludes 𝐾₅ as a minor, is quadratic in 𝑛, more specifically Ω(𝑛²). Since every 𝑛-vertex graph in a proper minor closed family has O(𝑛) edges, the rectilinear crossing number of all such graphs is trivially O(𝑛²). In fact, it is not hard to argue that O(𝑛) bound on the crossing number is the best one can hope for general enough proper minor-closed families of graphs and that to achieve O(𝑛) bounds, one has to both exclude a minor and bound the maximum degree of the graphs in the family. In this thesis, we do that for bounded degree graphs that exclude a single-crossing graph as a minor. A single-crossing graph is a graph whose crossing number is at most one. The main result of this thesis states that every graph 𝐺 that does not contain a single-crossing graph as a minor has a rectilinear crossing number O(∆𝑛), where 𝐺 has 𝑛 vertices and maximum degree ∆. This dependence on 𝑛 and ∆ is best possible. Note that each planar graph is a single-crossing graph, as is the complete graph 𝐾₅ and the complete bipartite graph 𝐾₃,₃. Thus, the result applies to 𝐾₅-minor-free graphs, 𝐾₃,₃-minor free graphs, as well as to bounded treewidth graphs. In the case of bounded treewidth graphs, the result improves on the previous best known bound of O(∆² · 𝑛) by Wood and Telle [New York Journal of Mathematics, 2007]. In the case of 𝐾₃,₃-minor free graphs, our result generalizes the result of Dujmovic, Kawarabayashi, Mohar and Wood [SCG 2008].

No description available.

Este trabalho tem por objetivo estudar os problemas computacionais que surgem ao se relacionar grafos com superfícies bidimensionais, dando especial atenção aos problemas do número de cruzamentos mínimo no plano (CROSSING NUMBER) e a problemas relacionados ao desenho de grafos em livros. Apresentamos uma redução do problema MULTICUT para CROSSING NUMBER, além de um resultado de complexidade em grafos de comparabilidade baseado em um resultado conhecido para desenhos em livros. / The objective of this text is to study computational problems that emerge from the relation between graphs and bidimensional surfaces, giving special attention to the crossing number problem and graph drawings on books. We present a reduction from MULTICUT to CROSSING NUMBER, in addition to a complexity result on comparability graphs based on a known result about drawings on books.

Este trabalho tem por objetivo estudar os problemas computacionais que surgem ao se relacionar grafos com superfícies bidimensionais, dando especial atenção aos problemas do número de cruzamentos mínimo no plano (CROSSING NUMBER) e a problemas relacionados ao desenho de grafos em livros. Apresentamos uma redução do problema MULTICUT para CROSSING NUMBER, além de um resultado de complexidade em grafos de comparabilidade baseado em um resultado conhecido para desenhos em livros. / The objective of this text is to study computational problems that emerge from the relation between graphs and bidimensional surfaces, giving special attention to the crossing number problem and graph drawings on books. We present a reduction from MULTICUT to CROSSING NUMBER, in addition to a complexity result on comparability graphs based on a known result about drawings on books.

Let F be a family of sets. A graph G is an intersection graph of sets from the family F if there exists a mapping f : V (G)→ F such that, An interval graph is an intersection graph of a family of closed intervals on the real line. Interval graphs find application in diverse fields ranging from DNA analysis to VLSI design. An interval on the real line can be generalized to a k dimensional box or k-box. A k-box B = (R1.R2….Rk) is defined to be the Cartesian product R1 × R2 × …× Rk, where each Ri is a closed interval on the real line. If each Ri is a unit length interval, we call B a k-cube. Thus, an interval is a 1-box and a unit length interval is a 1-cube. A graph G has a k-box representation, if G is an intersection graph of a family of k-boxes in Rk. Similarly, G has a k-cube representation, if G is an intersection graph of a family of k-cubes in Rk. The boxicity of G, denoted by box(G), is the minimum positive integer k such that G has a k-box representation. Similarly, the cubicity of G, denoted by cub(G), is the minimum positive integer k such that G has a k-cube representation. Thus, interval graphs are the graphs with boxicity equal to 1 and unit interval graphs are the graphs with cubicity equal to 1. The concepts of boxicity and cubicity were introduced by F.S. Roberts in 1969. Deciding whether the boxicity (or cubicity) of a graph is at most k is NP-complete even for a small positive integer k. Box representation of graphs finds application in niche overlap (competition) in ecology and to problems of fleet maintenance in operations research. Given a low dimensional box representation, some well known NP-hard problems become polynomial time solvable. Attempts to find efficient box and cube representations for special classes of graphs can be seen in the literature. Scheinerman [6] showed that the boxicity of outerplanar graphs is at most 2. Thomassen [7] proved that the boxicity of planar graphs is bounded from above by 3. Cube representations of special classes of graphs like hypercubes and complete multipartite graphs were investigated in [5, 3, 4]. In this thesis, we present several bounds for boxicity and cubicity of special classes of graphs in terms of other graph parameters. The following are the main results shown in this work. 1. It was shown in [2] that, for a graph G with maximum degree Δ, cub(G) ≤ [4(Δ+ 1) log n]. We show that, for a k-degenerate graph G, cub(G) ≤ (k + 2)[2e log n]. Since k is at most Δ and can be much lower, this clearly is a stronger result. This bound is tight up to a constant factor. 2. For a k-degenerate graph G, we give an efficient deterministic algorithm that runs in O(n2k) time to output an O(k log n) dimensional cube representation. 3. Crossing number of a graph G is the minimum number of crossing pairs of edges, over all drawings of G in the plane. We show that if crossing number of G is t, then box(G) is O(t1/4 log3/4 t). This bound is tight up to a factor of O((log t)1/4 ). 4. We prove that almost all graphs have cubicity O(dav log n), where dav denotes the average degree. 5. Boxicity of a k-leaf power is at most k -1. For every k, there exist k-leaf powers whose boxicity is exactly k - 1. Since leaf powers are a subclass of strongly chordal graphs, this result implies that there exist strongly chordal graphs with arbitrarily high boxicity 6. Otachi et al. [8] conjectured that chordal bipartite graphs (CBGs) have boxicity at most 2. We disprove this conjecture by exhibiting an infinite family of CBGs that have unbounded boxicity. We first prove that the bipartite power of a tree (which is a CBG) is a CBG and then show that there exist trees whose bipartite powers have high boxicity. Later in Chapter ??, we prove a more generic result in bipartite powering. We prove that, for every k ≥ 3, the bipartite power of a bipartite, k-chordal graph is bipartite and k-chordal thus implying that CBGs are closed under bipartite powering. 7. Boxicity of a line graph with maximum degree Δ is O(Δ log2 log2 Δ). This is a log2 Δ log log Δ factor improvement over the best known upper bound for boxicity of any graph [1]. We also prove a non-trivial lower bound for the boxicity of a d-dimensional hypercube.

Planar graphs have a rich history that dates back to the 18th Century. They form one of the core concepts of graph theory. In computational graph theory, they offer broad advantages to algorithm design and many groundbreaking results are based on them. Formally, a given graph is either planar or non-planar. However, there exists a diverse set of established measures to estimate how far away from being planar any given graph is. In this thesis, we aim at evaluating and improving algorithms to compute these measures of non-planarity. Particularly, we study (1) the problem of finding a maximum planar subgraph, i.e., a planar subgraph with the least number of edges removed; (2) the problem of embedding a graph on a lowest possible genus surface; and finally (3) the problem of drawing a graph such that there are as few edge crossings as possible. These problems constitute classical questions studied in graph drawing and each of them is NP-hard. Still, exact (exponential time) algorithms for them are of high interest and have been subject to study for decades. We propose novel mathematical programming models, based on different planarity criteria, to compute maximum planar subgraphs and low-genus embeddings. The key aspect of our most successful new models is that they carefully describe also the relation between embedded (sub-)graphs and their duals. Based on these models, we design algorithms that beat the respective state-of-the-art by orders of magnitude. We back these claims by extensive computational studies and rigorously show the theoretical advantages of our new models. Besides exact algorithms, we consider heuristic and approximate approaches to the maximum planar subgraph problem. Furthermore, in the realm of crossing numbers, we present an automated proof extraction to easily verify the crossing number of any given graph; a new hardness result for a subproblem that arises, e.g., when enumerating simple drawings; and resolve a conjecture regarding high node degree in minimal obstructions for low crossing number.