BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Steven Chaplick

Steven Chaplick contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational GeometryDiscrete MathematicsData Structures and Algorithms

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
3topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

10 published item(s)

preprint2022arXiv

Morphing Rectangular Duals

A rectangular dual of a plane graph $G$ is a contact representations of $G$ by interior-disjoint axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. A rectangular dual gives rise to a regular edge labeling (REL), which captures the orientations of the rectangle contacts. We study the problem of morphing between two rectangular duals of the same plane graph. If we require that, at any time throughout the morph, there is a rectangular dual, then a morph exists only if the two rectangular duals realize the same REL. Therefore, we allow intermediate contact representations of non-rectangular polygons of constant complexity. Given an $n$-vertex plane graph, we show how to compute in $O(n^3)$ time a piecewise linear morph that consists of $O(n^2)$ linear morphing steps.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Upward-Planar L-Drawings of Graphs

In an upward-planar L-drawing of a directed acyclic graph (DAG) each edge $e$ is represented as a polyline composed of a vertical segment with its lowest endpoint at the tail of $e$ and of a horizontal segment ending at the head of $e$. Distinct edges may overlap, but not cross. Recently, upward-planar L-drawings have been studied for $st$-graphs, i.e., planar DAGs with a single source $s$ and a single sink $t$ containing an edge directed from $s$ to $t$. It is known that a plane $st$-graph, i.e., an embedded $st$-graph in which the edge $(s,t)$ is incident to the outer face, admits an upward-planar L-drawing if and only if it admits a bitonic $st$-ordering, which can be tested in linear time. We study upward-planar L-drawings of DAGs that are not necessarily $st$-graphs. On the combinatorial side, we show that a plane DAG admits an upward-planar L-drawing if and only if it is a subgraph of a plane $st$-graph admitting a bitonic $st$-ordering. This allows us to show that not every tree with a fixed bimodal embedding admits an upward-planar L-drawing. Moreover, we prove that any acyclic cactus with a single source (or a single sink) admits an upward-planar L-drawing, which respects a given outerplanar embedding if there are no transitive edges. On the algorithmic side, we consider DAGs with a single source (or a single sink). We give linear-time testing algorithms for these DAGs in two cases: (i) when the drawing must respect a prescribed embedding and (ii) when no restriction is given on the embedding, but it is biconnected and series-parallel.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Parameterized Algorithms for Upward Planarity

We obtain new parameterized algorithms for the classical problem of determining whether a directed acyclic graph admits an upward planar drawing. Our results include a new fixed-parameter algorithm parameterized by the number of sources, an XP-algorithm parameterized by treewidth, and a fixed-parameter algorithm parameterized by treedepth. All three algorithms are obtained using a novel framework for the problem that combines SPQR tree-decompositions with parameterized techniques. Our approach unifies and pushes beyond previous tractability results for the problem on series-parallel digraphs, single-source digraphs and outerplanar digraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Drawing Graphs with Circular Arcs and Right-Angle Crossings

In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that admit such drawings are RAC graphs. RAC graphs are beyond-planar graphs and have been studied extensively. In particular, it is known that a RAC graph with n vertices has at most 4n - 10 edges. We introduce a superclass of RAC graphs, which we call arc-RAC graphs. A graph is arc-RAC if it admits a drawing where edges are represented by circular arcs and crossings form right angles. We provide a Turán-type result showing that an arc-RAC graph with n vertices has at most 14n - 12 edges and that there are n-vertex arc-RAC graphs with 4.5n - o(n) edges.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Intersection Graphs of Non-crossing Paths

We study graph classes modeled by families of non-crossing (NC) connected sets. Two classic graph classes in this context are disk graphs and proper interval graphs. We focus on the cases when the sets are paths and the host is a tree (generalizing proper interval graphs). Forbidden induced subgraph characterizations and linear time certifying recognition algorithms are given for intersection graphs of NC paths of a tree (and related subclasses). A direct consequence of our certifying algorithms is a linear time algorithm certifying the presence/absence of an induced claw $(K_{1,3})$ in a chordal graph. For the intersection graphs of NC paths of a tree, we characterize the minimum connected dominating sets (leading to a linear time algorithm to compute one). We further observe that there is always an independent dominating set which is a minimum dominating set, leading to the dominating set problem being solvable in linear time. Finally, each such graph $G$ is shown to have a Hamiltonian cycle if and only if it is 2-connected, and when $G$ is not 2-connected, a minimum-leaf spanning tree of $G$ has $\ell$ leaves if and only if $G$'s block-cutpoint tree has exactly $\ell$ leaves (e.g., implying that the block-cutpoint tree is a path if and only if the graph has a Hamiltonian path).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Layered Fan-Planar Graph Drawings

In this paper, we study fan-planar drawings that use $h$ layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testing the existence of such drawings is fixed-parameter tractable in $h$, via a reduction to a similar result for planar graphs by Dujmović et al. If the embedding is not fixed, then we give partial results for $h=2$: It was already known how to test existence of fan-planar proper 2-layer drawings for 2-connected graphs, and we show here how to test this for trees. Along the way, we exhibit other interesting results for graphs with a fan-planar proper $h$-layer drawings; in particular we bound their pathwidth and show that they have a bar-1-visibility representation.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Planar L-Drawings of Bimodal Graphs

In a planar L-drawing of a directed graph (digraph) each edge e is represented as a polyline composed of a vertical segment starting at the tail of e and a horizontal segment ending at the head of e. Distinct edges may overlap, but not cross. Our main focus is on bimodal graphs, i.e., digraphs admitting a planar embedding in which the incoming and outgoing edges around each vertex are contiguous. We show that every plane bimodal graph without 2-cycles admits a planar L-drawing. This includes the class of upward-plane graphs. Finally, outerplanar digraphs admit a planar L-drawing - although they do not always have a bimodal embedding - but not necessarily with an outerplanar embedding.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Recognizing Stick Graphs with and without Length Constraints

Stick graphs are intersection graphs of horizontal and vertical line segments that all touch a line of slope -1 and lie above this line. De Luca et al. [GD'18] considered the recognition problem of stick graphs when no order is given (STICK), when the order of either one of the two sets is given (STICK_A), and when the order of both sets is given (STICK_AB). They showed how to solve STICK_AB efficiently. In this paper, we improve the running time of their algorithm, and we solve STICK_A efficiently. Further, we consider variants of these problems where the lengths of the sticks are given as input. We show that these variants of STICK, STICK_A, and STICK_AB are all NP-complete. On the positive side, we give an efficient solution for STICK_AB with fixed stick lengths if there are no isolated vertices.

0 citations0 reviewsNo code linkedOpen access