Search

A square-contact representation of a planar graph $G=(V,E)$ maps vertices in $V$ to interior-disjoint axis-aligned squares in the plane and edges in $E$ to adjacencies between the sides of the corresponding squares. In this paper, we study proper square-contact representations of planar graphs, in which any two squares are either disjoint or share infinitely many points. We characterize the partial $2$-trees and the triconnected cycle-trees allowing for such representations. For partial $2$-trees our characterization uses a simple forbidden subgraph whose structure forces a separating triangle in any embedding. For the triconnected cycle-trees, a subclass of the triconnected simply-nested graphs, we use a new structural decomposition for the graphs in this family, which may be of independent interest. Finally, we study square-contact representations of general triconnected simply-nested graphs with respect to their outerplanarity index., Comment: 21 pages, 12 figures, extended version of "Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs" (The 28th International Symposium on Algorithms and Computation, 2017)

We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of producing a final output, an algorithm attempts to maintain an output close to the correct output for the current state of the data, repeatedly updating its best estimate of a correct output over time. We show that a simple repeated insertion-sort algorithm can maintain an O(n) Kendall tau distance, with high probability, between a maintained list and an underlying total order of n items in an evolving data model where each comparison is followed by a swap between a random consecutive pair of items in the underlying total order. This result is asymptotically optpimal, since there is an Omega(n) lower bound for Kendall tau distance for this problem. Our result closes the gap between this lower bound and the previous best algorithm for this problem, which maintains a Kendall tau distance of O(n log log n) with high probability. It also confirms previous experimental results that suggested that insertion sort tends to perform better than quicksort in practice.

We empirically study sorting in the evolving data model. In this model, a sorting algorithm maintains an approximation to the sorted order of a list of data items while simultaneously, with each comparison made by the algorithm, an adversary randomly swaps the order of adjacent items in the true sorted order. Previous work studies only two versions of quicksort, and has a gap between the lower bound of Omega(n) and the best upper bound of O(n log log n). The experiments we perform in this paper provide empirical evidence that some quadratic-time algorithms such as insertion sort and bubble sort are asymptotically optimal for any constant rate of random swaps. In fact, these algorithms perform as well as or better than algorithms such as quicksort that are more efficient in the traditional algorithm analysis model.

We introduce and study the online house numbering problem, where houses are added arbitrarily along a road and must be assigned labels to maintain their ordering along the road. The online house numbering problem is related to classic online list labeling problems, except that the optimization goal here is to minimize the maximum number of times that any house is relabeled. We provide several algorithms that achieve interesting tradeoffs between upper bounds on the number of maximum relabels per element and the number of bits used by labels.

We study various versions of the problem of scheduling platoons of autonomous vehicles through an unregulated intersection, where an algorithm must schedule which platoons should wait so that others can go through, so as to minimize the maximum delay for any vehicle. We provide polynomial-time algorithms for constructing such schedules for a $k$-way merge intersection, for constant $k$, and for a crossing intersection involving two-way traffic. We also show that the more general problem of scheduling autonomous platoons through an intersection that includes both a $k$-way merge, for non-constant $k$, and a crossing of two-way traffic is NP-complete.

We investigate the computational complexity of the exponential random graph model (ERGM) commonly used in social network analysis. This model represents a probability distribution on graphs by setting the log-likelihood of generating a graph to be a weighted sum of feature counts. These log-likelihoods must be exponentiated and then normalized to produce probabilities, and the normalizing constant is called the \emph{partition function}. We show that the problem of computing the partition function is $\mathsf{\#P}$-hard, and inapproximable in polynomial time to within an exponential ratio, assuming $\mathsf{P} \neq \mathsf{NP}$. Furthermore, there is no randomized polynomial time algorithm for generating random graphs whose distribution is within total variation distance $1-o(1)$ of a given ERGM. Our proofs use standard feature types based on the sociological theories of assortative mixing and triadic closure.

We study geometric data structures for sets of point-based temporal events, answering time-windowed queries, i.e., given a contiguous time interval we answer common geometric queries about the point events with time stamps in this interval. The geometric queries we consider include queries based on the skyline, convex hull, and proximity relations of the point set. We provide space efficient data structures which answer queries in polylogarithmic time., CCCG 2014