BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

David Eppstein

David Eppstein appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational GeometryData Structures and Algorithmsmath.CODiscrete MathematicsSocial and Information Networksmath.MGComputational Complexityphysics.soc-phcond-mat.dis-nnCryptography and SecurityDistributed, Parallel, and Cluster ComputingFormal Languages and Automata TheoryGraphicsmath.DGmath.GTMultimedianlin.CGOther Computer ScienceSoftware Engineering

Catalog footprint

What is connected

110works
19topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

110 published item(s)

preprint2025arXiv

Noncrossing Longest Paths and Cycles

Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.

0 citations0 reviewsNo code linkedOpen access
preprint2024arXiv

Computational Complexities of Folding

We prove several hardness results on folding origami crease patterns. Flat-folding finite crease patterns is fixed-parameter tractable in the ply of the folded pattern (how many layers overlap at any point) and the treewidth of an associated cell adjacency graph. Under the exponential time hypothesis, the singly-exponential dependence of our algorithm on treewidth is necessary, even for bounded ply. Improving the dependence on ply would require progress on the unsolved map folding problem. Finding the shape of a polyhedron folded from a net with triangular faces and integer edge lengths is not possible in algebraic computation tree models of computation that at each tree node allow either the computation of arbitrary integer roots of real numbers, or the extraction of roots of polynomials with bounded degree and integer coefficients. For a model of reconfigurable origami with origami squares are attached at one edge by a hinge to a rigid surface, moving from one flat-folded state to another by changing the position of one square at a time is PSPACE-complete, and counting flat-folded states is #P-complete. For self-similar square crease patterns with infinitely many folds, testing flat-foldability is undecidable.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

On the complexity of embedding in graph products

Graph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of embedding a graph $G$ in a host graph that is the strong product of a path $P$ with a graph $H$ that satisfies some properties, such as having small treewidth, pathwidth or tree depth. We show that this is NP-hard, even under numerous restrictions on both $G$ and $H$. In particular, computing the row pathwidth and the row treedepth is NP-hard even for a tree of small pathwidth, while computing the row treewidth is NP-hard even for series-parallel graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Reflections in an octagonal mirror maze

Suppose we are given an environment consisting of axis-parallel and diagonal line segments with integer endpoints, each of which may be reflective or non-reflective, with integer endpoints, and an initial position for a light ray passing through points of the integer grid. Then in time polynomial in the number of segments and in the number of bits needed to specify the coordinates of the input, we can determine the eventual fate of the reflected ray.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Parameterized Complexity of Finding Subgraphs with Hereditary Properties on Hereditary Graph Classes

We investigate the parameterized complexity of finding subgraphs with hereditary properties on graphs belonging to a hereditary graph class. Given a graph $G$, a non-trivial hereditary property $Π$ and an integer parameter $k$, the general problem $P(G,Π,k)$ asks whether there exists $k$ vertices of $G$ that induce a subgraph satisfying property $Π$. This problem, $P(G,Π,k)$ has been proved to be NP-complete by Lewis and Yannakakis. The parameterized complexity of this problem is shown to be W[1]-complete by Khot and Raman, if $Π$ includes all trivial graphs but not all complete graphs and vice versa; and is fixed-parameter tractable (FPT), otherwise. As the problem is W[1]-complete on general graphs when $Π$ includes all trivial graphs but not all complete graphs and vice versa, it is natural to further investigate the problem on restricted graph classes. Motivated by this line of research, we study the problem on graphs which also belong to a hereditary graph class and establish a framework which settles the parameterized complexity of the problem for various hereditary graph classes. In particular, we show that: $P(G,Π,k)$ is solvable in polynomial time when the graph $G$ is co-bipartite and $Π$ is the property of being planar, bipartite or triangle-free (or vice-versa). $P(G,Π,k)$ is FPT when the graph $G$ is planar, bipartite or triangle-free and $Π$ is the property of being planar, bipartite or triangle-free, or graph $G$ is co-bipartite and $Π$ is the property of being co-bipartite. $P(G,Π,k)$ is W[1]-complete when the graph $G$ is $C_4$-free, $K_{1,4}$-free or a unit disk graph and $Π$ is the property of being either planar or bipartite.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Acutely Triangulated, Stacked, and Very Ununfoldable Polyhedra

We present new examples of topologically convex edge-ununfoldable polyhedra, i.e., polyhedra that are combinatorially equivalent to convex polyhedra, yet cannot be cut along their edges and unfolded into one planar piece without overlap. One family of examples is acutely triangulated, i.e., every face is an acute triangle. Another family of examples is stacked, i.e., the result of face-to-face gluings of tetrahedra. Both families achieve another natural property, which we call very ununfoldable: for every $k$, there is an example such that every nonoverlapping multipiece edge unfolding has at least $k$ pieces.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Low-stretch spanning trees of graphs with bounded width

We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph $G$ with a linear arrangement of bandwidth $b$ can be embedded into a distribution $\mathcal T$ of spanning trees such that the expected stretch of each edge of $G$ is $O(b^2)$. Our proof implies a linear time algorithm for sampling from $\mathcal T$. Therefore, we have a linear time algorithm that finds a spanning tree of $G$ with average stretch $O(b^2)$ with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of $G$ with average stretch $O(b^3)$. For graphs of cutwidth $c$, we construct a spanning tree with stretch $O(c^2)$ in linear time. Finally, when $G$ has treewidth $k$ we provide a dynamic programming algorithm computing a minimum stretch spanning tree of $G$ that runs in polynomial time with respect to the number of vertices of $G$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the treewidth of Hanoi graphs

The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Parameterized Leaf Power Recognition via Embedding into Graph Products

The $k$-leaf power graph $G$ of a tree $T$ is a graph whose vertices are the leaves of $T$ and whose edges connect pairs of leaves at unweighted distance at most~$k$ in $T$. Recognition of the $k$-leaf power graphs for $k \geq 7$ is still an open problem. In this paper, we provide two algorithms for this problem for sparse leaf power graphs. Our results shows that the problem of recognizing these graphs is fixed-parameter tractable when parameterized both by $k$ and by the degeneracy of the given graph. To prove this, we first describe how to embed the leaf root of a leaf power graph into a product of the graph with a cycle graph. We bound the treewidth of the resulting product in terms of $k$ and the degeneracy of $G$. The first presented algorithm uses methods based on monadic second-order logic (MSO$_2$) to recognize the existence of a leaf power as a subgraph of the product graph. Using the same embedding in the product graph, the second algorithm presents a dynamic programming approach to solve the problem and provide a better dependence on the parameters.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Reactive Proximity Data Structures for Graphs

We consider data structures for graphs where we maintain a subset of the nodes called sites, and allow proximity queries, such as asking for the closest site to a query node, and update operations that enable or disable nodes as sites. We refer to a data structure that can efficiently react to such updates as reactive. We present novel reactive proximity data structures for graphs of polynomial expansion, i.e., the class of graphs with small separators, such as planar graphs and road networks. Our data structures can be used in several logistical problems and geographic information systems dealing with real-time data, such as emergency dispatching. We experimentally compare our data structure to Dijkstra's algorithm in a system emulating random queries in a real road network.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Simplifying Activity-on-Edge Graphs

We formalize the simplification of activity-on-edge graphs used for visualizing project schedules, where the vertices of the graphs represent project milestones, and the edges represent either tasks of the project or timing constraints between milestones. In this framework, a timeline of the project can be constructed as a leveled drawing of the graph, where the levels of the vertices represent the time at which each milestone is scheduled to happen. We focus on the following problem: given an activity-on-edge graph representing a project, find an equivalent activity-on-edge graph (one with the same critical paths) that has the minimum possible number of milestone vertices among all equivalent activity-on-edge graphs. We provide a polynomial-time algorithm for solving this graph minimization problem.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Stable-Matching Voronoi Diagrams: Combinatorial Complexity and Algorithms

We study algorithms and combinatorial complexity bounds for \emph{stable-matching Voronoi diagrams}, where a set, $S$, of $n$ point sites in the plane determines a stable matching between the points in $\mathbb{R}^2$ and the sites in $S$ such that (i) the points prefer sites closer to them and sites prefer points closer to them, and (ii) each site has a quota or "appetite" indicating the area of the set of points that can be matched to it. Thus, a stable-matching Voronoi diagram is a solution to the well-known post office problem with the added (realistic) constraint that each post office has a limit on the size of its jurisdiction. Previous work on the stable-matching Voronoi diagram provided existence and uniqueness proofs, but did not analyze its combinatorial or algorithmic complexity. In this paper, we show that a stable-matching Voronoi diagram of $n$ point sites has $O(n^{2+\varepsilon})$ faces and edges, for any $\varepsilon>0$, and show that this bound is almost tight by giving a family of diagrams with $Θ(n^2)$ faces and edges. We also provide a discrete algorithm for constructing it in $O(n^3\log n+n^2f(n))$ time in the real-RAM model of computation, where $f(n)$ is the runtime of a geometric primitive (which we define) that can be approximated numerically, but cannot, in general, be performed exactly in an algebraic model of computation. We show, however, how to compute the geometric primitive exactly for polygonal convex distance functions.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Face flips in origami tessellations

Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of the plane) with a mountain-valley (MV) assignment $μ:E\to\{-1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $F$ of $G$ to create a new MV assignment $μ_F$ which equals $μ$ except for all creases $e$ bordering $F$, where we have $μ_F(e)=-μ(e)$. In this paper we explore the configuration space of face flips for a variety of crease patterns $G$ that are tilings of the plane, proving examples where $μ_F$ results in a MV assignment that is either never, sometimes, or always flat-foldable for various choices of $F$. We also consider the problem of finding, given two foldable MV assignments $μ_1$ and $μ_2$ of a given crease pattern $G$, a minimal sequence of face flips to turn $μ_1$ into $μ_2$. We find polynomial-time algorithms for this in the cases where $G$ is either a square grid or the Miura-ori, and show that this problem is NP-hard in the case where $G$ is the triangle lattice.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Grid peeling and the affine curve-shortening flow

In this paper we study an experimentally-observed connection between two seemingly unrelated processes, one from computational geometry and the other from differential geometry. The first one (which we call "grid peeling") is the convex-layer decomposition of subsets $G\subset \mathbb Z^2$ of the integer grid, previously studied for the particular case $G=\{1,\ldots,m\}^2$ by Har-Peled and Lidický (2013). The second one is the affine curve-shortening flow (ACSF), first studied by Alvarez et al. (1993) and Sapiro and Tannenbaum (1993). We present empirical evidence that, in a certain well-defined sense, grid peeling behaves at the limit like ACSF on convex curves. We offer some theoretical arguments in favor of this conjecture. We also pay closer attention to the simple case where $G=\mathbb N^2$ is a quarter-infinite grid. This case corresponds to ACSF starting with an infinite L-shaped curve, which when transformed using the ACSF becomes a hyperbola for all times $t>0$. We prove that, in the grid peeling of $\mathbb N^2$, (1) the number of grid points removed up to iteration $n$ is $Θ(n^{3/2}\log n)$; and (2) the boundary at iteration $n$ is sandwiched between two hyperbolas that are separated from each other by a constant factor.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect

We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary transformations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration and sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE-completeness of the following decision problems: $\bullet$ Given two satisfying assignments to a planar monotone instance of Not-All-Equal 3-SAT, can one assignment be transformed into the other by single variable `flips' (assignment changes), preserving satisfiability at every step? $\bullet$ Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum? $\bullet$ Given two points in $\{0,1\}^n$ contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n-hypercube connecting the two points and contained in P? These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the instances of the NP problems that appear as input to the reconfiguration problems in our reductions can be shown to lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Convex-Arc Drawings of Pseudolines

A weak pseudoline arrangement is a topological generalization of a line arrangement, consisting of curves topologically equivalent to lines that cross each other at most once. We consider arrangements that are outerplanar---each crossing is incident to an unbounded face---and simple---each crossing point is the crossing of only two curves. We show that these arrangements can be represented by chords of a circle, by convex polygonal chains with only two bends, or by hyperbolic lines. Simple but non-outerplanar arrangements (non-weak) can be represented by convex polygonal chains or convex smooth curves of linear complexity.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Cuckoo Filter: Simplification and Analysis

The cuckoo filter data structure of Fan, Andersen, Kaminsky, and Mitzenmacher (CoNEXT 2014) performs the same approximate set operations as a Bloom filter in less memory, with better locality of reference, and adds the ability to delete elements as well as to insert them. However, until now it has lacked theoretical guarantees on its performance. We describe a simplified version of the cuckoo filter using fewer hash function calls per query. With this simplification, we provide the first theoretical performance guarantees on cuckoo filters, showing that they succeed with high probability whenever their fingerprint length is large enough.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Distance-Sensitive Planar Point Location

Let $\mathcal{S}$ be a connected planar polygonal subdivision with $n$ edges that we want to preprocess for point-location queries, and where we are given the probability $γ_i$ that the query point lies in a polygon $P_i$ of $\mathcal{S}$. We show how to preprocess $\mathcal{S}$ such that the query time for a point~$p\in P_i$ depends on~$γ_i$ and, in addition, on the distance from $p$ to the boundary of~$P_i$---the further away from the boundary, the faster the query. More precisely, we show that a point-location query can be answered in time $O\left(\min \left(\log n, 1 + \log \frac{\mathrm{area}(P_i)}{γ_i Δ_{p}^2}\right)\right)$, where $Δ_{p}$ is the shortest Euclidean distance of the query point~$p$ to the boundary of $P_i$. Our structure uses $O(n)$ space and $O(n \log n)$ preprocessing time. It is based on a decomposition of the regions of $\mathcal{S}$ into convex quadrilaterals and triangles with the following property: for any point $p\in P_i$, the quadrilateral or triangle containing~$p$ has area $Ω(Δ_{p}^2)$. For the special case where $\mathcal{S}$ is a subdivision of the unit square and $γ_i=\mathrm{area}(P_i)$, we present a simpler solution that achieves a query time of $O\left(\min \left(\log n, \log \frac{1}{Δ_{p}^2}\right)\right)$. The latter solution can be extended to convex subdivisions in three dimensions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Models and Algorithms for Graph Watermarking

We introduce models and algorithmic foundations for graph watermarking. Our frameworks include security definitions and proofs, as well as characterizations when graph watermarking is algorithmically feasible, in spite of the fact that the general problem is NP-complete by simple reductions from the subgraph isomorphism or graph edit distance problems. In the digital watermarking of many types of files, an implicit step in the recovery of a watermark is the mapping of individual pieces of data, such as image pixels or movie frames, from one object to another. In graphs, this step corresponds to approximately matching vertices of one graph to another based on graph invariants such as vertex degree. Our approach is based on characterizing the feasibility of graph watermarking in terms of keygen, marking, and identification functions defined over graph families with known distributions. We demonstrate the strength of this approach with exemplary watermarking schemes for two random graph models, the classic Erdős-Rényi model and a random power-law graph model, both of which are used to model real-world networks.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Simple Recognition of Halin Graphs and Their Generalizations

We describe and implement two local reduction rules that can be used to recognize Halin graphs in linear time, avoiding the complicated planarity testing step of previous linear time Halin graph recognition algorithms. The same two rules can be used as the basis for linear-time algorithms for other algorithmic problems on Halin graphs, including decomposing these graphs into a tree and a cycle, finding a Hamiltonian cycle, or constructing a planar embedding. These reduction rules can also be used to recognize a broader class of polyhedral graphs. These graphs, which we call the D3-reducible graphs, are the dual graphs of the polyhedra formed by gluing pyramids together on their triangular faces; their treewidth is bounded, and they necessarily have Lombardi drawings.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Spanning Trees in Multipartite Geometric Graphs

Let $R$ and $B$ be two disjoint sets of points in the plane where the points of $R$ are colored red and the points of $B$ are colored blue, and let $n=|R\cup B|$. A bichromatic spanning tree is a spanning tree in the complete bipartite geometric graph with bipartition $(R,B)$. The minimum (respectively maximum) bichromatic spanning tree problem is the problem of computing a bichromatic spanning tree of minimum (respectively maximum) total edge length. 1. We present a simple algorithm that solves the minimum bichromatic spanning tree problem in $O(n\log^3 n)$ time. This algorithm can easily be extended to solve the maximum bichromatic spanning tree problem within the same time bound. It also can easily be generalized to multicolored point sets. 2. We present $Θ(n\log n)$-time algorithms that solve the minimum and the maximum bichromatic spanning tree problems. 3. We extend the bichromatic spanning tree algorithms and solve the multicolored version of these problems in $O(n\log n\log k)$ time, where $k$ is the number of different colors (or the size of the multipartition in a complete multipartite geometric graph).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Approximate Greedy Clustering and Distance Selection for Graph Metrics

$\newcommand{\eps}{\varepsilon}$ In this paper, we consider two important problems defined on finite metric spaces, and provide efficient new algorithms and approximation schemes for these problems on inputs given as graph shortest path metrics or high-dimensional Euclidean metrics. The first of these problems is the greedy permutation (or farthest-first traversal) of a finite metric space: a permutation of the points of the space in which each point is as far as possible from all previous points. We describe randomized algorithms to find $(1+\eps)$-approximate greedy permutations of any graph with $n$ vertices and $m$ edges in expected time $O(\eps^{-1}(m+n)\log n\log(n/\eps))$, and to find $(1+\eps)$-approximate greedy permutations of points in high-dimensional Euclidean spaces in expected time $O(\eps^{-2} n^{1+1/(1+\eps)^2 + o(1)})$. Additionally we describe a deterministic algorithm to find exact greedy permutations of any graph with $n$ vertices and treewidth $O(1)$ in worst-case time $O(n^{3/2}\log^{O(1)} n)$. The second of the two problems we consider is distance selection: given $k \in [ \binom{n}{2} ]$, we are interested in computing the $k$th smallest distance in the given metric space. We show that for planar graph metrics one can approximate this distance, up to a constant factor, in near linear time.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Confluent Orthogonal Drawings of Syntax Diagrams

We provide a pipeline for generating syntax diagrams (also called railroad diagrams) from context free grammars. Syntax diagrams are a graphical representation of a context free language, which we formalize abstractly as a set of mutually recursive nondeterministic finite automata and draw by combining elements from the confluent drawing, layered drawing, and smooth orthogonal drawing styles. Within our pipeline we introduce several heuristics that modify the grammar but preserve the language, improving the aesthetics of the final drawing.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Contact Representations of Sparse Planar Graphs

We study representations of graphs by contacts of circular arcs, CCA-representations for short, where the vertices are interior-disjoint circular arcs in the plane and each edge is realized by an endpoint of one arc touching the interior of another. A graph is (2,k)-sparse if every s-vertex subgraph has at most 2s - k edges, and (2, k)-tight if in addition it has exactly 2n - k edges, where n is the number of vertices. Every graph with a CCA- representation is planar and (2, 0)-sparse, and it follows from known results on contacts of line segments that for k >= 3 every (2, k)-sparse graph has a CCA-representation. Hence the question of CCA-representability is open for (2, k)-sparse graphs with 0 <= k <= 2. We partially answer this question by computing CCA-representations for several subclasses of planar (2,0)-sparse graphs. In particular, we show that every plane (2, 2)-sparse graph has a CCA-representation, and that any plane (2, 1)-tight graph or (2, 0)-tight graph dual to a (2, 3)-tight graph or (2, 4)-tight graph has a CCA-representation. Next, we study CCA-representations in which each arc has an empty convex hull. We characterize the plane graphs that have such a representation, based on the existence of a special orientation of the graph edges. Using this characterization, we show that every plane graph of maximum degree 4 has such a representation, but that finding such a representation for a plane (2, 0)-tight graph with maximum degree 5 is an NP-complete problem. Finally, we describe a simple algorithm for representing plane (2, 0)-sparse graphs with wedges, where each vertex is represented with a sequence of two circular arcs (straight-line segments).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Drawing Trees with Perfect Angular Resolution and Polynomial Area

We study methods for drawing trees with perfect angular resolution, i.e., with angles at each node v equal to 2π/d(v). We show: 1. Any unordered tree has a crossing-free straight-line drawing with perfect angular resolution and polynomial area. 2. There are ordered trees that require exponential area for any crossing-free straight-line drawing having perfect angular resolution. 3. Any ordered tree has a crossing-free Lombardi-style drawing (where each edge is represented by a circular arc) with perfect angular resolution and polynomial area. Thus, our results explore what is achievable with straight-line drawings and what more is achievable with Lombardi-style drawings, with respect to drawings of trees with perfect angular resolution.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Planar Induced Subgraphs of Sparse Graphs

We show that every graph has an induced pseudoforest of at least $n-m/4.5$ vertices, an induced partial 2-tree of at least $n-m/5$ vertices, and an induced planar subgraph of at least $n-m/5.2174$ vertices. These results are constructive, implying linear-time algorithms to find the respective induced subgraphs. We also show that the size of the largest $K_h$-minor-free graph in a given graph can sometimes be at most $n-m/6+o(m)$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Rigid Origami Vertices: Conditions and Forcing Sets

We develop an intrinsic necessary and sufficient condition for single-vertex origami crease patterns to be able to fold rigidly. We classify such patterns in the case where the creases are pre-assigned to be mountains and valleys as well as in the unassigned case. We also illustrate the utility of this result by applying it to the new concept of minimal forcing sets for rigid origami models, which are the smallest collection of creases that, when folded, will force all the other creases to fold in a prescribed way.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Rooted Cycle Bases

A cycle basis in an undirected graph is a minimal set of simple cycles whose symmetric differences include all Eulerian subgraphs of the given graph. We define a rooted cycle basis to be a cycle basis in which all cycles contain a specified root edge, and we investigate the algorithmic problem of constructing rooted cycle bases. We show that a given graph has a rooted cycle basis if and only if the root edge belongs to its 2-core and the 2-core is 2-vertex-connected, and that constructing such a basis can be performed efficiently. We show that in an unweighted or positively weighted graph, it is possible to find the minimum weight rooted cycle basis in polynomial time. Additionally, we show that it is NP-complete to find a fundamental rooted cycle basis (a rooted cycle basis in which each cycle is formed by combining paths in a fixed spanning tree with a single additional edge) but that the problem can be solved by a fixed-parameter-tractable algorithm when parameterized by clique-width.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Treetopes and their Graphs

We define treetopes, a generalization of the three-dimensional roofless polyhedra (Halin graphs) to arbitrary dimensions. Like roofless polyhedra, treetopes have a designated base facet such that every face of dimension greater than one intersects the base in more than one point. We prove an equivalent characterization of the 4-treetopes using the concept of clustered planarity from graph drawing, and we use this characterization to recognize the graphs of 4-treetopes in polynomial time. This result provides one of the first classes of 4-polytopes, other than pyramids and stacked polytopes, that can be recognized efficiently from their graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

ERGMs are Hard

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Folding a Paper Strip to Minimize Thickness

In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Linear-time Algorithms for Proportional Apportionment

The apportionment problem deals with the fair distribution of a discrete set of $k$ indivisible resources (such as legislative seats) to $n$ entities (such as parties or geographic subdivisions). Highest averages methods are a frequently used class of methods for solving this problem. We present an $O(n)$-time algorithm for performing apportionment under a large class of highest averages methods. Our algorithm works for all highest averages methods used in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Superpatterns and Universal Point Sets

An old open problem in graph drawing asks for the size of a universal point set, a set of points that can be used as vertices for straight-line drawings of all n-vertex planar graphs. We connect this problem to the theory of permutation patterns, where another open problem concerns the size of superpatterns, permutations that contain all patterns of a given size. We generalize superpatterns to classes of permutations determined by forbidden patterns, and we construct superpatterns of size n^2/4 + Theta(n) for the 213-avoiding permutations, half the size of known superpatterns for unconstrained permutations. We use our superpatterns to construct universal point sets of size n^2/4 - Theta(n), smaller than the previous bound by a 9/16 factor. We prove that every proper subclass of the 213-avoiding permutations has superpatterns of size O(n log^O(1) n), which we use to prove that the planar graphs of bounded pathwidth have near-linear universal point sets.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The Galois Complexity of Graph Drawing: Why Numerical Solutions are Ubiquitous for Force-Directed, Spectral, and Circle Packing Drawings

Many well-known graph drawing techniques, including force directed drawings, spectral graph layouts, multidimensional scaling, and circle packings, have algebraic formulations. However, practical methods for producing such drawings ubiquitously use iterative numerical approximations rather than constructing and then solving algebraic expressions representing their exact solutions. To explain this phenomenon, we use Galois theory to show that many variants of these problems have solutions that cannot be expressed by nested radicals or nested roots of low-degree polynomials. Hence, such solutions cannot be computed exactly even in extended computational models that include such operations.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket

We study wear-leveling techniques for cuckoo hashing, showing that it is possible to achieve a memory wear bound of $\log\log n+O(1)$ after the insertion of $n$ items into a table of size $Cn$ for a suitable constant $C$ using cuckoo hashing. Moreover, we study our cuckoo hashing method empirically, showing that it significantly improves on the memory wear performance for classic cuckoo hashing and linear probing in practice.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Antimatroids and Balanced Pairs

We generalize the 1/3-2/3 conjecture from partially ordered sets to antimatroids: we conjecture that any antimatroid has a pair of elements x,y such that x has probability between 1/3 and 2/3 of appearing earlier than y in a uniformly random basic word of the antimatroid. We prove the conjecture for antimatroids of convex dimension two (the antimatroid-theoretic analogue of partial orders of width two), for antimatroids of height two, for antimatroids with an independent element, and for the perfect elimination antimatroids and node search antimatroids of several classes of graphs. A computer search shows that the conjecture is true for all antimatroids with at most six elements.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Combinatorial Pair Testing: Distinguishing Workers from Slackers

We formalize a problem we call combinatorial pair testing (CPT), which has applications to the identification of uncooperative or unproductive participants in pair programming, massively distributed computing, and crowdsourcing environments. We give efficient adaptive and nonadaptive CPT algorithms and we show that our methods use an optimal number of testing rounds to within constant factors. We also provide an empirical evaluation of some of our methods.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Confluent Hasse diagrams

We show that a transitively reduced digraph has a confluent upward drawing if and only if its reachability relation has order dimension at most two. In this case, we construct a confluent upward drawing with $O(n^2)$ features, in an $O(n) \times O(n)$ grid in $O(n^2)$ time. For the digraphs representing series-parallel partial orders we show how to construct a drawing with $O(n)$ features in an $O(n) \times O(n)$ grid in $O(n)$ time from a series-parallel decomposition of the partial order. Our drawings are optimal in the number of confluent junctions they use.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Diamond-Kite Adaptive Quadrilateral Meshing

We describe a family of quadrilateral meshes based on diamonds, rhombi with 60 and 120 degree angles, and kites with 60, 90, and 120 degree angles, that can be adapted to a local size function by local subdivision operations. Our meshes use a number of elements that is within a constant factor of the minimum possible for any mesh of bounded aspect ratio elements, graded by the same local size function, and is invariant under Laplacian smoothing. The vertices of our meshes form the centers of the circles in a pair of dual circle packings. The same vertex placement algorithm but a different mesh topology gives a pair of dual well-centered meshes adapted to the given size function.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Drawing Arrangement Graphs In Small Grids, Or How To Play Planarity

We describe a linear-time algorithm that finds a planar drawing of every graph of a simple line or pseudoline arrangement within a grid of area O(n^{7/6}). No known input causes our algorithm to use area Ω(n^{1+ε}) for any ε>0; finding such an input would represent significant progress on the famous k-set problem from discrete geometry. Drawing line arrangement graphs is the main task in the Planarity puzzle.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fixed parameter tractability of crossing minimization of almost-trees

We investigate exact crossing minimization for graphs that differ from trees by a small number of additional edges, for several variants of the crossing minimization problem. In particular, we provide fixed parameter tractable algorithms for the 1-page book crossing number, the 2-page book crossing number, and the minimum number of crossed edges in 1-page and 2-page book drawings.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Near-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets

We describe an algorithm that takes as input n points in the plane and a parameter ε, and produces as output an embedded planar graph having the given points as a subset of its vertices in which the graph distances are a (1 + ε)-approximation to the geometric distances between the given points. For point sets in which the Delaunay triangulation has bounded sharpest angle, our algorithm's output has O(n) vertices, its weight is O(1) times the minimum spanning tree weight, and the algorithm's running time is bounded by O(n \sqrt{log log n}). We use this result in a similarly fast deterministic approximation scheme for the traveling salesperson problem.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Set-Difference Range Queries

We introduce the problem of performing set-difference range queries, where answers to queries are set-theoretic symmetric differences between sets of items in two geometric ranges. We describe a general framework for answering such queries based on a novel use of data-streaming sketches we call signed symmetric-difference sketches. We show that such sketches can be realized using invertible Bloom filters (IBFs), which can be composed, differenced, and searched so as to solve set-difference range queries in a wide range of scenarios.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Small Superpatterns for Dominance Drawing

We exploit the connection between dominance drawings of directed acyclic graphs and permutations, in both directions, to provide improved bounds on the size of universal point sets for certain types of dominance drawing and on superpatterns for certain natural classes of permutations. In particular we show that there exist universal point sets for dominance drawings of the Hasse diagrams of width-two partial orders of size O(n^{3/2}), universal point sets for dominance drawings of st-outerplanar graphs of size O(n\log n), and universal point sets for dominance drawings of directed trees of size O(n^2). We show that 321-avoiding permutations have superpatterns of size O(n^{3/2}), riffle permutations (321-, 2143-, and 2413-avoiding permutations) have superpatterns of size O(n), and the concatenations of sequences of riffles and their inverses have superpatterns of size O(n\log n). Our analysis includes a calculation of the leading constants in these bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Strict Confluent Drawing

We define strict confluent drawing, a form of confluent drawing in which the existence of an edge is indicated by the presence of a smooth path through a system of arcs and junctions (without crossings), and in which such a path, if it exists, must be unique. We prove that it is NP-complete to determine whether a given graph has a strict confluent drawing but polynomial to determine whether it has an outerplanar strict confluent drawing with a fixed vertex ordering (a drawing within a disk, with the vertices placed in a given order on the boundary).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Force-Directed Graph Drawing Using Social Gravity and Scaling

Force-directed layout algorithms produce graph drawings by resolving a system of emulated physical forces. We present techniques for using social gravity as an additional force in force-directed layouts, together with a scaling technique, to produce drawings of trees and forests, as well as more complex social networks. Social gravity assigns mass to vertices in proportion to their network centrality, which allows vertices that are more graph-theoretically central to be visualized in physically central locations. Scaling varies the gravitational force throughout the simulation, and reduces crossings relative to unscaled gravity. In addition to providing this algorithmic framework, we apply our algorithms to social networks produced by Mark Lombardi, and we show how social gravity can be incorporated into force-directed Lombardi-style drawings.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Planar Lombardi Drawings for Subcubic Graphs

We prove that every planar graph with maximum degree three has a planar drawing in which the edges are drawn as circular arcs that meet at equal angles around every vertex. Our construction is based on the Koebe-Thurston-Andreev circle packing theorem, and uses a novel type of Voronoi diagram for circle packings that is invariant under Moebius transformations, defined using three-dimensional hyperbolic geometry. We also use circle packing to construct planar Lombardi drawings of a special class of 4-regular planar graphs, the medial graphs of polyhedral graphs, and we show that not every 4-regular planar graph has a Lombardi drawing. We have implemented our algorithm for 3-connected planar cubic graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Graphs of Planar Soap Bubbles

We characterize the graphs formed by two-dimensional soap bubbles as being exactly the 3-regular bridgeless planar multigraphs. Our characterization combines a local characterization of soap bubble graphs in terms of the curvatures of arcs meeting at common vertices, a proof that this characterization remains invariant under Moebius transformations, an application of Moebius invariance to prove bridgelessness, and a Moebius-invariant power diagram of circles previously developed by the author for its applications in graph drawing.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Windows into Relational Events: Data Structures for Contiguous Subsequences of Edges

We consider the problem of analyzing social network data sets in which the edges of the network have timestamps, and we wish to analyze the subgraphs formed from edges in contiguous subintervals of these timestamps. We provide data structures for these problems that use near-linear preprocessing time, linear space, and sublogarithmic query time to handle queries that ask for the number of connected components, number of components that contain cycles, number of vertices whose degree equals or is at most some predetermined value, number of vertices that can be reached from a starting set of vertices by time-increasing paths, and related queries.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Adjacency-Preserving Spatial Treemaps

Rectangular layouts, subdivisions of an outer rectangle into smaller rectangles, have many applications in visualizing spatial information, for instance in rectangular cartograms in which the rectangles represent geographic or political regions. A spatial treemap is a rectangular layout with a hierarchical structure: the outer rectangle is subdivided into rectangles that are in turn subdivided into smaller rectangles. We describe algorithms for transforming a rectangular layout that does not have this hierarchical structure, together with a clustering of the rectangles of the layout, into a spatial treemap that respects the clustering and also respects to the extent possible the adjacencies of the input layout.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Bounds on the Complexity of Halfspace Intersections when the Bounded Faces have Small Dimension

We study the combinatorial complexity of D-dimensional polyhedra defined as the intersection of n halfspaces, with the property that the highest dimension of any bounded face is much smaller than D. We show that, if d is the maximum dimension of a bounded face, then the number of vertices of the polyhedron is O(n^d) and the total number of bounded faces of the polyhedron is O(n^d^2). For inputs in general position the number of bounded faces is O(n^d). For any fixed d, we show how to compute the set of all vertices, how to determine the maximum dimension of a bounded face of the polyhedron, and how to compute the set of bounded faces in polynomial time, by solving a polynomial number of linear programs.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Full)

A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad-hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Short)

A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad-hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Listing All Maximal Cliques in Large Sparse Real-World Graphs

We implement a new algorithm for listing all maximal cliques in sparse graphs due to Eppstein, Löffler, and Strash (ISAAC 2010) and analyze its performance on a large corpus of real-world graphs. Our analysis shows that this algorithm is the first to offer a practical solution to listing all maximal cliques in large sparse graphs. All other theoretically-fast algorithms for sparse graphs have been shown to be significantly slower than the algorithm of Tomita et al. (Theoretical Computer Science, 2006) in practice. However, the algorithm of Tomita et al. uses an adjacency matrix, which requires too much space for large sparse graphs. Our new algorithm opens the door for fast analysis of large sparse graphs whose adjacency matrix will not fit into working memory.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Optimally fast incremental Manhattan plane embedding and planar tight span construction

We describe a data structure, a rectangular complex, that can be used to represent hyperconvex metric spaces that have the same topology (although not necessarily the same distance function) as subsets of the plane. We show how to use this data structure to construct the tight span of a metric space given as an n x n distance matrix, when the tight span is homeomorphic to a subset of the plane, in time O(n^2), and to add a single point to a planar tight span in time O(n). As an application of this construction, we show how to test whether a given finite metric space embeds isometrically into the Manhattan plane in time O(n^2), and add a single point to the space and re-test whether it has such an embedding in time O(n).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Privacy-Enhanced Methods for Comparing Compressed DNA Sequences

In this paper, we study methods for improving the efficiency and privacy of compressed DNA sequence comparison computations, under various querying scenarios. For instance, one scenario involves a querier, Bob, who wants to test if his DNA string, $Q$, is close to a DNA string, $Y$, owned by a data owner, Alice, but Bob does not want to reveal $Q$ to Alice and Alice is willing to reveal $Y$ to Bob \emph{only if} it is close to $Q$. We describe a privacy-enhanced method for comparing two compressed DNA sequences, which can be used to achieve the goals of such a scenario. Our method involves a reduction to set differencing, and we describe a privacy-enhanced protocol for set differencing that achieves absolute privacy for Bob (in the information theoretic sense), and a quantifiable degree of privacy protection for Alice. One of the important features of our protocols, which makes them ideally suited to privacy-enhanced DNA sequence comparison problems, is that the communication complexity of our solutions is proportional to a threshold that bounds the cardinality of the set differences that are of interest, rather than the cardinality of the sets involved (which correlates to the length of the DNA sequences). Moreover, in our protocols, the querier, Bob, can easily compute the set difference only if its cardinality is close to or below a specified threshold.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Randomized Speedup of the Bellman-Ford Algorithm

We describe a variant of the Bellman-Ford algorithm for single-source shortest paths in graphs with negative edges but no negative cycles that randomly permutes the vertices and uses this randomized order to process the vertices within each pass of the algorithm. The modification reduces the worst-case expected number of relaxation steps of the algorithm, compared to the previously-best variant by Yen (1970), by a factor of 2/3 with high probability. We also use our high probability bound to add negative cycle detection to the randomized algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Tracking Moving Objects with Few Handovers

We study the online problem of assigning a moving point to a base-station region that contains it. For instance, the moving object could represent a cellular phone and the base station could represent the coverage zones of cell towers. Our goal is to minimize the number of handovers that occur when the point moves outside its assigned region and must be assigned to a new region. We study this problem in terms of competitive analysis and we measure the competitive ratio of our algorithms as a function of the ply of the system of regions, that is, the maximum number of regions that cover any single point. In the offline version of this problem, when object motions are known in advance, a simple greedy strategy suffices to determine an optimal assignment of objects to base stations, with as few handovers as possible. For the online version of this problem for moving points in one dimension, we present a deterministic algorithm that achieves a competitive ratio of O(log ply) with respect to the optimal algorithm, and we show that no better ratio is possible. For two or more dimensions, we present a randomized online algorithm that achieves a competitive ratio of O(log ply) with respect to the optimal algorithm, and a deterministic algorithm that achieves a competitive ratio of O(ply); again, we show that no better ratio is possible.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Cloning Voronoi Diagrams via Retroactive Data Structures

We address the problem of replicating a Voronoi diagram $V(S)$ of a planar point set $S$ by making proximity queries, which are of three possible (in decreasing order of information content): 1. the exact location of the nearest site(s) in $S$; 2. the distance to and label(s) of the nearest site(s) in $S$; 3. a unique label for every nearest site in $S$. We provide algorithms showing how queries of Type 1 and Type 2 allow an exact cloning of $V(S)$ with $O(n)$ queries and $O(n \log^2 n)$ processing time. We also prove that queries of Type 3 can never exactly clone $V(S)$, but we show that with $O(n \log\frac{1}ε)$ queries we can construct an $ε$-approximate cloning of $V(S)$. In addition to showing the limits of nearest-neighbor database security, our methods also provide one of the first natural algorithmic applications of retroactive data structures.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Densities of Minor-Closed Graph Families

We define the limiting density of a minor-closed family of simple graphs F to be the smallest number k such that every n-vertex graph in F has at most kn(1+o(1)) edges, and we investigate the set of numbers that can be limiting densities. This set of numbers is countable, well-ordered, and closed; its order type is at least ω^ω. It is the closure of the set of densities of density-minimal graphs, graphs for which no minor has a greater ratio of edges to vertices. By analyzing density-minimal graphs of low densities, we find all limiting densities up to the first two cluster points of the set of limiting densities, 1 and 3/2. For multigraphs, the only possible limiting densities are the integers and the superparticular ratios i/(i+1).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Dilation, smoothed distance, and minimization diagrams of convex functions

We study Voronoi diagrams for distance functions that add together two convex functions, each taking as its argument the difference between Cartesian coordinates of two planar points. When the functions do not grow too quickly, then the Voronoi diagram has linear complexity and can be constructed in near-linear randomized expected time. Additionally, the level sets of the distances from the sites form a family of pseudocircles in the plane, all cells in the Voronoi diagram are connected, and the set of bisectors separating any one cell in the diagram from each of the others forms an arrangement of pseudolines in the plane. We apply these results to the smoothed distance or biotope transform metric, a geometric analogue of the Jaccard distance whose Voronoi diagrams can be used to determine the dilation of a star network with a given hub. For sufficiently closely spaced points in the plane, the Voronoi diagram of smoothed distance has linear complexity and can be computed efficiently. We also experiment with a variant of Lloyd's algorithm, adapted to smoothed distance, to find uniformly spaced point samples with exponentially decreasing density around a given point.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Drawing Graphs in the Plane with a Prescribed Outer Face and Polynomial Area

We study the classic graph drawing problem of drawing a planar graph using straight-line edges with a prescribed convex polygon as the outer face. Unlike previous algorithms for this problem, which may produce drawings with exponential area, our method produces drawings with polynomial area. In addition, we allow for collinear points on the boundary, provided such vertices do not create overlapping edges. Thus, we solve an open problem of Duncan et al., which, when combined with their work, implies that we can produce a planar straight-line drawing of a combinatorially-embedded genus-g graph with the graph's canonical polygonal schema drawn as a convex polygonal external face.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Extended h-Index Parameterized Data Structures for Computing Dynamic Subgraph Statistics

We present techniques for maintaining subgraph frequencies in a dynamic graph, using data structures that are parameterized in terms of h, the h-index of the graph. Our methods extend previous results of Eppstein and Spiro for maintaining statistics for undirected subgraphs of size three to directed subgraphs and to subgraphs of size four. For the directed case, we provide a data structure to maintain counts for all 3-vertex induced subgraphs in O(h) amortized time per update. For the undirected case, we maintain the counts of size-four subgraphs in O(h^2) amortized time per update. These extensions enable a number of new applications in Bioinformatics and Social Networking research.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Flows in One-Crossing-Minor-Free Graphs

We study the maximum flow problem in directed H-minor-free graphs where H can be drawn in the plane with one crossing. If a structural decomposition of the graph as a clique-sum of planar graphs and graphs of constant complexity is given, we show that a maximum flow can be computed in O(n log n) time. In particular, maximum flows in directed K_{3,3}-minor-free graphs and directed K_5-minor-free graphs can be computed in O(n log n) time without additional assumptions.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Listing All Maximal Cliques in Sparse Graphs in Near-optimal Time

The degeneracy of an $n$-vertex graph $G$ is the smallest number $d$ such that every subgraph of $G$ contains a vertex of degree at most $d$. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron--Kerbosch algorithm and show that it runs in time $O(dn3^{d/3})$. We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an $n$-vertex graph with degeneracy $d$ (when $d$ is a multiple of 3 and $n\ge d+3$) is $(n-d)3^{d/3}$. Therefore, our algorithm matches the $Θ(d(n-d)3^{d/3})$ worst-case output size of the problem whenever $n-d=Ω(n)$.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Lombardi Drawings of Graphs

We introduce the notion of Lombardi graph drawings, named after the American abstract artist Mark Lombardi. In these drawings, edges are represented as circular arcs rather than as line segments or polylines, and the vertices have perfect angular resolution: the edges are equally spaced around each vertex. We describe algorithms for finding Lombardi drawings of regular graphs, graphs of bounded degeneracy, and certain families of planar graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Optimal 3D Angular Resolution for Low-Degree Graphs

We show that every graph of maximum degree three can be drawn in three dimensions with at most two bends per edge, and with 120-degree angles between any two edge segments meeting at a vertex or a bend. We show that every graph of maximum degree four can be drawn in three dimensions with at most three bends per edge, and with 109.5-degree angles, i.e., the angular resolution of the diamond lattice, between any two edge segments meeting at a vertex or bend.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Privacy-Preserving Data-Oblivious Geometric Algorithms for Geographic Data

We give efficient data-oblivious algorithms for several fundamental geometric problems that are relevant to geographic information systems, including planar convex hulls and all-nearest neighbors. Our methods are "data-oblivious" in that they don't perform any data-dependent operations, with the exception of operations performed inside low-level blackbox circuits having a constant number of inputs and outputs. Thus, an adversary who observes the control flow of one of our algorithms, but who cannot see the inputs and outputs to the blackbox circuits, cannot learn anything about the input or output. This behavior makes our methods applicable to secure multiparty computation (SMC) protocols for geographic data used in location-based services. In SMC protocols, multiple parties wish to perform a computation on their combined data without revealing individual data to the other parties. For instance, our methods can be used to solve a problem posed by Du and Atallah, where Alice has a set, A, of m private points in the plane, Bob has another set, B, of n private points in the plane, and Alice and Bob want to jointly compute the convex hull of A u B without disclosing any more information than what can be derived from the answer. In particular, neither Alice nor Bob want to reveal any of their respective points that are in the interior of the convex hull of A u B.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Ramified rectilinear polygons: coordinatization by dendrons

Simple rectilinear polygons (i.e. rectilinear polygons without holes or cutpoints) can be regarded as finite rectangular cell complexes coordinatized by two finite dendrons. The intrinsic $l_1$-metric is thus inherited from the product of the two finite dendrons via an isometric embedding. The rectangular cell complexes that share this same embedding property are called ramified rectilinear polygons. The links of vertices in these cell complexes may be arbitrary bipartite graphs, in contrast to simple rectilinear polygons where the links of points are either 4-cycles or paths of length at most 3. Ramified rectilinear polygons are particular instances of rectangular complexes obtained from cube-free median graphs, or equivalently simply connected rectangular complexes with triangle-free links. The underlying graphs of finite ramified rectilinear polygons can be recognized among graphs in linear time by a Lexicographic Breadth-First-Search. Whereas the symmetry of a simple rectilinear polygon is very restricted (with automorphism group being a subgroup of the dihedral group $D_4$), ramified rectilinear polygons are universal: every finite group is the automorphism group of some ramified rectilinear polygon.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Regular Labelings and Geometric Structures

Three types of geometric structure---grid triangulations, rectangular subdivisions, and orthogonal polyhedra---can each be described combinatorially by a regular labeling: an assignment of colors and orientations to the edges of an associated maximal or near-maximal planar graph. We briefly survey the connections and analogies between these three kinds of labelings, and their uses in designing efficient geometric algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Combinatorics and geometry of finite and infinite squaregraphs

Squaregraphs were originally defined as finite plane graphs in which all inner faces are quadrilaterals (i.e., 4-cycles) and all inner vertices (i.e., the vertices not incident with the outer face) have degrees larger than three. The planar dual of a finite squaregraph is determined by a triangle-free chord diagram of the unit disk, which could alternatively be viewed as a triangle-free line arrangement in the hyperbolic plane. This representation carries over to infinite plane graphs with finite vertex degrees in which the balls are finite squaregraphs. Algebraically, finite squaregraphs are median graphs for which the duals are finite circular split systems. Hence squaregraphs are at the crosspoint of two dualities, an algebraic and a geometric one, and thus lend themselves to several combinatorial interpretations and structural characterizations. With these and the 5-colorability theorem for circle graphs at hand, we prove that every squaregraph can be isometrically embedded into the Cartesian product of five trees. This embedding result can also be extended to the infinite case without reference to an embedding in the plane and without any cardinality restriction when formulated for median graphs free of cubes and further finite obstructions. Further, we exhibit a class of squaregraphs that can be embedded into the product of three trees and we characterize those squaregraphs that are embeddable into the product of just two trees. Finally, finite squaregraphs enjoy a number of algorithmic features that do not extend to arbitrary median graphs. For instance, we show that median-generating sets of finite squaregraphs can be computed in polynomial time, whereas, not unexpectedly, the corresponding problem for median graphs turns out to be NP-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Growth and Decay in Life-Like Cellular Automata

We propose a four-way classification of two-dimensional semi-totalistic cellular automata that is different than Wolfram's, based on two questions with yes-or-no answers: do there exist patterns that eventually escape any finite bounding box placed around them? And do there exist patterns that die out completely? If both of these conditions are true, then a cellular automaton rule is likely to support spaceships, small patterns that move and that form the building blocks of many of the more complex patterns that are known for Life. If one or both of these conditions is not true, then there may still be phenomena of interest supported by the given cellular automaton rule, but we will have to look harder for them. Although our classification is very crude, we argue that it is more objective than Wolfram's (due to the greater ease of determining a rigorous answer to these questions), more predictive (as we can classify large groups of rules without observing them individually), and more accurate in focusing attention on rules likely to support patterns with complex behavior. We support these assertions by surveying a number of known cellular automaton rules.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Edge Crossings

We provide linear-time algorithms for geometric graphs with sublinearly many crossings. That is, we provide algorithms running in O(n) time on connected geometric graphs having n vertices and k crossings, where k is smaller than n by an iterated logarithmic factor. Specific problems we study include Voronoi diagrams and single-source shortest paths. Our algorithms all run in linear time in the standard comparison-based computational model; hence, we make no assumptions about the distribution or bit complexities of edge weights, nor do we utilize unusual bit-level operations on memory words. Instead, our algorithms are based on a planarization method that "zeroes in" on edge crossings, together with methods for extending planar separator decompositions to geometric graphs with sublinearly many crossings. Incidentally, our planarization algorithm also solves an open computational geometry problem of Chazelle for triangulating a self-intersecting polygonal chain having n segments and k crossings in linear time, for the case when k is sublinear in n by an iterated logarithmic factor.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Steinitz Theorems for Orthogonal Polyhedra

We define a simple orthogonal polyhedron to be a three-dimensional polyhedron with the topology of a sphere in which three mutually-perpendicular edges meet at each vertex. By analogy to Steinitz's theorem characterizing the graphs of convex polyhedra, we find graph-theoretic characterizations of three classes of simple orthogonal polyhedra: corner polyhedra, which can be drawn by isometric projection in the plane with only one hidden vertex, xyz polyhedra, in which each axis-parallel line through a vertex contains exactly one other vertex, and arbitrary simple orthogonal polyhedra. In particular, the graphs of xyz polyhedra are exactly the bipartite cubic polyhedral graphs, and every bipartite cubic polyhedral graph with a 4-connected dual graph is the graph of a corner polyhedron. Based on our characterizations we find efficient algorithms for constructing orthogonal polyhedra from their graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

The h-Index of a Graph and its Application to Dynamic Subgraph Statistics

We describe a data structure that maintains the number of triangles in a dynamic undirected graph, subject to insertions and deletions of edges and of degree-zero vertices. More generally it can be used to maintain the number of copies of each possible three-vertex subgraph in time O(h) per update, where h is the h-index of the graph, the maximum number such that the graph contains $h$ vertices of degree at least h. We also show how to maintain the h-index itself, and a collection of h high-degree vertices in the graph, in constant time per update. Our data structure has applications in social network analysis using the exponential random graph model (ERGM); its bound of O(h) time per edge is never worse than the Theta(sqrt m) time per edge necessary to list all triangles in a static graph, and is strictly better for graphs obeying a power law degree distribution. In order to better understand the behavior of the h-index statistic and its implications for the performance of our algorithms, we also study the behavior of the h-index on a set of 136 real-world networks.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing

We consider embeddings of 3-regular graphs into 3-dimensional Cartesian coordinates, in such a way that two vertices are adjacent if and only if two of their three coordinates are equal (that is, if they lie on an axis-parallel line) and such that no three points lie on the same axis-parallel line; we call a graph with such an embedding an xyz graph}. We describe a correspondence between xyz graphs and face-colored embeddings of the graph onto two-dimensional manifolds, and we relate bipartiteness of the xyz graph to orientability of the underlying topological surface. Using this correspondence, we show that planar graphs are xyz graphs if and only if they are bipartite, cubic, and three-connected, and that it is NP-complete to determine whether an arbitrary graph is an xyz graph. We also describe an algorithm with running time O(n 2^{n/2}) for testing whether a given graph is an xyz graph.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Improved Combinatorial Group Testing Algorithms for Real-World Problem Sizes

We study practically efficient methods for performing combinatorial group testing. We present efficient non-adaptive and two-stage combinatorial group testing algorithms, which identify the at most d items out of a given set of n items that are defective, using fewer tests for all practical set sizes. For example, our two-stage algorithm matches the information theoretic lower bound for the number of tests in a combinatorial group testing regimen.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

All Maximal Independent Sets and Dynamic Dominance for Sparse Graphs

We describe algorithms, based on Avis and Fukuda's reverse search paradigm, for listing all maximal independent sets in a sparse graph in polynomial time and delay per output. For bounded degree graphs, our algorithms take constant time per set generated; for minor-closed graph families, the time is O(n) per set, and for more general sparse graph families we achieve subquadratic time per set. We also describe new data structures for maintaining a dynamic vertex set S in a sparse or minor-closed graph family, and querying the number of vertices not dominated by S; for minor-closed graph families the time per update is constant, while it is sublinear for any sparse graph family. We can also maintain a dynamic vertex set in an arbitrary m-edge graph and test the independence of the maintained set in time O(sqrt m) per update. We use the domination data structures as part of our enumeration algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2004arXiv

The Effect of Faults on Network Expansion

In this paper we study the problem of how resilient networks are to node faults. Specifically, we investigate the question of how many faults a network can sustain so that it still contains a large (i.e. linear-sized) connected component that still has approximately the same expansion as the original fault-free network. For this we apply a pruning technique which culls away parts of the faulty network which have poor expansion. This technique can be applied to both adversarial faults and to random faults. For adversarial faults we prove that for every network with expansion alpha, a large connected component with basically the same expansion as the original network exists for up to a constant times alpha n faults. This result is tight in the sense that every graph G of size n and uniform expansion alpha(.), i.e. G has an expansion of alpha(n) and every subgraph G' of size m of G has an expansion of O(alpha(m)), can be broken into sublinear components with omega(alpha(n) n) faults. For random faults we observe that the situation is significantly different, because in this case the expansion of a graph only gives a very weak bound on its resilience to random faults. More specifically, there are networks of uniform expansion O(sqrt{n}) that are resilient against a constant fault probability but there are also networks of uniform expansion Omega(1/log n) that are not resilient against a O(1/log n) fault probability. Thus, a different parameter is needed. For this we introduce the span of a graph which allows us to determine the maximum fault probability in a much better way than the expansion can. We use the span to show the first known results for the effect of random faults on the expansion of d-dimensional meshes.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

A steady state model for graph power laws

Power law distribution seems to be an important characteristic of web graphs. Several existing web graph models generate power law graphs by adding new vertices and non-uniform edge connectivities to existing graphs. Researchers have conjectured that preferential connectivity and incremental growth are both required for the power law distribution. In this paper, we propose a different web graph model with power law distribution that does not require incremental growth. We also provide a comparison of our model with several others in their ability to predict web graph clustering behavior.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

3-Coloring in Time O(1.3289^n)

We consider worst case time bounds for NP-complete problems including 3-SAT, 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a constraint satisfaction (CSP) formulation of these problems. 3-SAT is equivalent to (2,3)-CSP while the other problems above are special cases of (3,2)-CSP; there is also a natural duality transformation from (a,b)-CSP to (b,a)-CSP. We give a fast algorithm for (3,2)-CSP and use it to improve the time bounds for solving the other problems listed above. Our techniques involve a mixture of Davis-Putnam-style backtracking with more sophisticated matching and network flow based ideas.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

Fast Approximation of Centrality

Social studies researchers use graphs to model group activities in social networks. An important property in this context is the centrality of a vertex: the inverse of the average distance to each other vertex. We describe a randomized approximation algorithm for centrality in weighted graphs. For graphs exhibiting the small world phenomenon, our method estimates the centrality of all vertices with high probability within a (1+epsilon) factor in near-linear time.

0 citations0 reviewsNo code linkedOpen access
preprint2000arXiv

Incremental and Decremental Maintenance of Planar Width

We present an algorithm for maintaining the width of a planar point set dynamically, as points are inserted or deleted. Our algorithm takes time O(kn^epsilon) per update, where k is the amount of change the update causes in the convex hull, n is the number of points in the set, and epsilon is any arbitrarily small constant. For incremental or decremental update sequences, the amortized time per update is O(n^epsilon).

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

Algorithms for Coloring Quadtrees

We describe simple linear time algorithms for coloring the squares of balanced and unbalanced quadtrees so that no two adjacent squares are given the same color. If squares sharing sides are defined as adjacent, we color balanced quadtrees with three colors, and unbalanced quadtrees with four colors; these results are both tight, as some quadtrees require this many colors. If squares sharing corners are defined as adjacent, we color balanced or unbalanced quadtrees with six colors; for some quadtrees, at least five colors are required.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

Diameter and Treewidth in Minor-Closed Graph Families

It is known that any planar graph with diameter D has treewidth O(D), and this fact has been used as the basis for several planar graph algorithms. We investigate the extent to which similar relations hold in other graph families. We show that treewidth is bounded by a function of the diameter in a minor-closed family, if and only if some apex graph does not belong to the family. In particular, the O(D) bound above can be extended to bounded-genus graphs. As a consequence, we extend several approximation algorithms and exact subgraph isomorphism algorithms from planar graphs to other graph families.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

Fast Hierarchical Clustering and Other Applications of Dynamic Closest Pairs

We develop data structures for dynamic closest pair problems with arbitrary distance functions, that do not necessarily come from any geometric structure on the objects. Based on a technique previously used by the author for Euclidean closest pairs, we show how to insert and delete objects from an n-object set, maintaining the closest pair, in O(n log^2 n) time per update and O(n) space. With quadratic space, we can instead use a quadtree-like structure to achieve an optimal time bound, O(n) per update. We apply these data structures to hierarchical clustering, greedy matching, and TSP heuristics, and discuss other potential applications in machine learning, Groebner bases, and local improvement algorithms for partition and placement problems. Experiments show our new methods to be faster in practice than previously used heuristics.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

Multivariate Regression Depth

The regression depth of a hyperplane with respect to a set of n points in R^d is the minimum number of points the hyperplane must pass through in a rotation to vertical. We generalize hyperplane regression depth to k-flats for any k between 0 and d-1. The k=0 case gives the classical notion of center points. We prove that for any k and d, deep k-flats exist, that is, for any set of n points there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1+epsilon)-approximation algorithm for the deepest flat.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

Regression Depth and Center Points

We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least ceiling(n/(d+1)). as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d dimensions there exists a point that cannot escape to infinity without crossing at least ceiling(n/(d+1)) hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

Setting Parameters by Example

We introduce a class of "inverse parametric optimization" problems, in which one is given both a parametric optimization problem and a desired optimal solution; the task is to determine parameter values that lead to the given solution. We describe algorithms for solving such problems for minimum spanning trees, shortest paths, and other "optimal subgraph" problems, and discuss applications in multicast routing, vehicle path planning, resource allocation, and board game programming.

0 citations0 reviewsNo code linkedOpen access
preprint1999arXiv

The Distribution of Cycle Lengths in Graphical Models for Iterative Decoding

This paper analyzes the distribution of cycle lengths in turbo decoding and low-density parity check (LDPC) graphs. The properties of such cycles are of significant interest in the context of iterative decoding algorithms which are based on belief propagation or message passing. We estimate the probability that there exist no simple cycles of length less than or equal to k at a randomly chosen node in a turbo decoding graph using a combination of counting arguments and independence assumptions. For large block lengths n, this probability is approximately e^{-{2^{k-1}-4}/n}, k>=4. Simulation results validate the accuracy of the various approximations. For example, for turbo codes with a block length of 64000, a randomly chosen node has a less than 1% chance of being on a cycle of length less than or equal to 10, but has a greater than 99.9% chance of being on a cycle of length less than or equal to 20. The effect of the "S-random" permutation is also analyzed and it is shown that while it eliminates short cycles of length k<8, it does not significantly affect the overall distribution of cycle lengths. Similar analyses and simulations are also presented for graphs for LDPC codes. The paper concludes by commenting briefly on how these results may provide insight into the practical success of iterative decoding methods.

0 citations0 reviewsNo code linkedOpen access
preprint1998arXiv

Linear Complexity Hexahedral Mesh Generation

We show that any polyhedron forming a topological ball with an even number of quadrilateral sides can be partitioned into O(n) topological cubes, meeting face to face. The result generalizes to non-simply-connected polyhedra satisfying an additional bipartiteness condition. The same techniques can also be used to reduce the geometric version of the hexahedral mesh generation problem to a finite case analysis amenable to machine solution.

0 citations0 reviewsNo code linkedOpen access