{'fraction_non_alphanumeric': 0.027626317702653582, 'fraction_numerical': 0.004362050163576881, 'mean_word_length': 4.47117296222664, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Combinatorial algorithms for graphs and partially ordered sets

In this thesis we study combinatorial and algorithmic problems for graphs and partially ordered sets. The thesis is centered around four themes: planar graphs, reachability, order dimension and special cases of NP-hard problems. The results presented are of both algorithmic and structural flavor. The thesis begins with an overview of the problems considered and an introduction to the necessary mathematical tools, whereafter the results are described in more detail. Thorup proved that we can label the vertices in a planar directed n-vertex graph with labels of size O(log n), such that reachability queries can be answered in constant time by inspecting only the labels of the two vertices in the query. In Chapter 2 we generalize Thorup’s labeling scheme to a setting where only a subset of the vertices are labeled. We prove that if the set of vertices we are interested in is a subset of the union of f faces, we can label the interesting vertices with labels of size O(log f), while still supporting constant time reachability queries. In particular, this yields an optimal labeling scheme for reachability in k-outerplanar digraphs for constant k. In Chapter 3 we study the combinatorial problem of replacing a directed graph and a set of interesting vertices with a graph of smaller size while preserving the existence of paths between the interesting vertices. We call such a new graph a reachability substitute, and we prove that finding a reachability substitute of minimum size is NP-hard. Furthermore, we show that for almost all graphs and sets of interesting vertices, no planar reachability substitute exists, not of any size. The dimension of a partially ordered set P is the minimum number of linear orders whose intersection is P, and the vertex-edge-face poset PM of a planar map M is the poset on the vertices, edges and faces of M ordered by inclusion. Brightwell and Trotter proved that dim(PM ) ≤ 4. In Chapter 4 we investigate the cases where dim(PM ) ≤ 3 and where dim(QM ) ≤ 3; here QM denotes the vertex-face poset of M , which is the subposet of PM induced by the vertices and faces of M . We show that a map M with dim(PM ) ≤ 3 must be outerplanar and have an outerplanar dual. We concentrate on the simplest class of such maps and prove that within this class dim(PM ) ≤ 3 is equivalent to the existence of a certain oriented coloring of a subset of the edges. This condition is easily checked and can be turned into a linear time algorithm returning a 3-realizer. Additionally, we prove that if M is 2-connected and M and M∗ are outerplanar, then dim(QM ) ≤ 3. There are, however, outerplanar maps with dim(QM) = 4. We construct the first such example.