Outer 1-Planar Graphs Auer, Christopher; Bachmaier, Christian; Brandenburg, Franz J. ...
Algorithmica,
04/2016, Volume:
74, Issue:
4
Journal Article
Peer reviewed
A graph is outer 1-planar (
o1p
) if it can be drawn in the plane such that all vertices are in the outer face and each edge is crossed at most once.
o1p
graphs generalize outerplanar graphs, which ...can be recognized in linear time, and specialize 1-planar graphs, whose recognition is
N
P
-hard. We explore
o1p
graphs. Our first main result is a linear-time algorithm that takes a graph as input and returns a positive or a negative witness for
o1p
. If a graph
G
is
o1p
, then the algorithm computes an embedding and can augment
G
to a maximal
o1p
graph. Otherwise,
G
includes one of six minors, which is detected by the recognition algorithm. Secondly, we establish structural properties of
o1p
graphs.
o1p
graphs are planar and are subgraphs of planar graphs with a Hamiltonian cycle. They are neither closed under edge contraction nor under subdivision. Several important graph parameters, such as treewidth, colorability, stack number, and queue number, increase by one from outerplanar to
o1p
graphs. Every
o1p
graph of size
n
has at most
5
2
n
-
4
edges and there are maximal
o1p
graphs with
11
5
n
-
18
5
edges, and these bounds are tight. Finally, every
o1p
graph has a straight-line grid drawing in
O
(
n
2
)
area with all vertices in the outer face, a planar visibility representation in
O
(
n
log
n
)
area, and a 3D straight-line drawing in linear volume, and these drawings can be constructed in linear time.
In recent years, significant advances have been made in the design and analysis of fully dynamic algorithms. However, these theoretical results have received very little attention from the practical ...perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. Here, we present a quick reference guide to recent engineering and theory results in the area of fully dynamic graph algorithms.
One of the most fundamental problems in computer science is the reachability problem: Given a directed graph and two vertices s and t, can sreach t via a path? We revisit existing techniques and ...combine them with new approaches to support a large portion of reachability queries in constant time using a linear-sized reachability index. Our new algorithm O’Reach can be easily combined with previously developed solutions for the problem or run standalone.In a detailed experimental study, we compare a variety of algorithms with respect to their index-building and query times as well as their memory footprint on a diverse set of instances. Our experiments indicate that the query performance often depends strongly not only on the type of graph but also on the result, i.e., reachable or unreachable. Furthermore, we show that previous algorithms are significantly sped up when combined with our new approach in almost all scenarios. Surprisingly, due to cache effects, a higher investment in space doesn’t necessarily pay off: Reachability queries can often be answered even faster than single memory accesses in a precomputed full reachability matrix.
A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end vertex. NIC-planarity generalizes ...IC-planarity, which allows a vertex to be incident to at most one crossing edge, and specializes 1-planarity, which only requires at most one crossing per edge.
We characterize embeddings of maximal NIC-planar graphs in terms of generalized planar dual graphs. The characterization is used to derive tight bounds on the density of maximal NIC-planar graphs which ranges between 3.2(n−2) and 3.6(n−2). Further, we prove that optimal NIC-planar graphs with 3.6(n−2) edges have a unique embedding and can be recognized in linear time, whereas the general recognition problem of NIC-planar graphs is NP-complete. In addition, we show that there are NIC-planar graphs that do not admit right angle crossing drawings, which distinguishes NIC-planar from IC-planar graphs.
Reconfigurable optical topologies promise to improve the performance in datacenters by dynamically optimizing the physical network in a demand-aware manner. State-of-the-art optical technologies ...allow to establish and update direct connectivity (in the form of edge-disjoint matchings) between top-of-rack switches within microseconds or less. However, to fully exploit temporal structure in the demand, such fine-grained reconfigurations also require fast algorithms for optimizing the interconnecting matchings.Motivated by the desire to offload a maximum amount of demand to the reconfigurable network, this paper initiates the study of fast algorithms to find k disjoint heavy matchings in graphs. We present and analyze six algorithms, based on iterative matchings, b-matching, edge coloring, and node-rankings. We show that the problem is generally {\mathcal{N}}{\mathcal{P}}{\text{ - hard}} and study the achievable approximation ratios.An extensive empirical evaluation of our algorithms on both real-world and synthetic traces (88 in total), including traces collected in Facebook datacenters and in HPC clusters reveals that all our algorithms provide high-quality matchings, and also very fast ones come within 95 % or more of the best solution. However, the running times differ significantly and what is the best algorithm depends on k and the acceptable runtime-quality tradeoff.
Emerging reconfigurable datacenters allow to dynamically adjust the network topology in a demand-aware manner. These datacenters rely on optical switches which can be reconfigured to provide direct ...connectivity between racks, in the form of edge-disjoint matchings. While state-of-the-art optical switches in principle support microsecond reconfigurations, the demand-aware topology optimization constitutes a bottleneck.This paper proposes a dynamic algorithms approach to improve the performance of reconfigurable datacenter networks, by supporting faster reactions to changes in the traffic demand. This approach leverages the temporal locality of traffic patterns in order to update the interconnecting matchings incrementally, rather than recomputing them from scratch. In particular, we present six (batch-)dynamic algorithms and compare them to static ones. We conduct an extensive empirical evaluation on 176 synthetic and 39 real-world traces, and find that dynamic algorithms can both significantly improve the running time and reduce the number of changes to the configuration, especially in networks with high temporal locality, while retaining matching weight.
PDF
