Author name cluster

Matias Korman

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

TCS Journal 2023 Journal Article

Graphs with large total angular resolution

Oswin Aichholzer
Matias Korman
Yoshio Okamoto
Irene Parada
Daniel Perz
André van Renssen
Birgit Vogtenhuber

The total angular resolution of a straight-line drawing is the minimum angle between two edges of the drawing. It combines two properties contributing to the readability of a drawing: the angular resolution, which is the minimum angle between incident edges, and the crossing resolution, which is the minimum angle between crossing edges. We consider the total angular resolution of a graph, which is the maximum total angular resolution of a straight-line drawing of this graph. We prove tight bounds for the number of edges for graphs for some values of the total angular resolution up to a finite number of well specified exceptions of constant size. In addition, we show that deciding whether a graph has total angular resolution at least 60 ∘ is NP-hard. Further we present some special graphs and their total angular resolution.

Details DOI

TCS Journal 2022 Journal Article

Reconfiguration of connected graph partitions via recombination

Hugo A. Akitaya
Matias Korman
Oliver Korten
Diane L. Souvaine
Csaba D. Tóth

Motivated by applications in gerrymandering detection, we study a reconfiguration problem on connected partitions of a connected graph G. A partition of V ( G ) is connected if every part induces a connected subgraph. In many applications, it is desirable to obtain parts of roughly the same size, possibly with some slack s. A Balanced Connected k -Partition with slack s, denoted ( k, s ) -BCP, is a partition of V ( G ) into k nonempty subsets, of sizes n 1, …, n k with | n i − n / k | ≤ s, each of which induces a connected subgraph (when s = 0, the k parts are perfectly balanced, and we call it k -BCP for short). A recombination is an operation that takes a ( k, s ) -BCP of a graph G and produces another by merging two adjacent subgraphs and repartitioning them. Given two k-BCPs, A and B, of G and a slack s ≥ 0, we wish to determine whether there exists a sequence of recombinations that transform A into B via ( k, s ) -BCPs. We obtain four results related to this problem: (1) When s is unbounded, the transformation is always possible using at most 6 ( k − 1 ) recombinations. (2) If G is Hamiltonian, the transformation is possible using O ( k n ) recombinations for any s ≥ n / k, (3) there exist negative instances for s ≤ n / ( 3 k ), and (4) we show that determining whether a sequence of recombination that connects two ( k, s ) -BCP of a graph G exists is PSPACE-complete when k ∈ O ( n ε ) and s ∈ O ( n 1 − ε ), for any constant 0 < ε ≤ 1. This statement holds even for restricted settings such as when G is an edge-maximal planar graph or when k ≥ 3 and G is planar.

Details DOI

TCS Journal 2021 Journal Article

Constrained routing between non-visible vertices

Prosenjit Bose
Matias Korman
André van Renssen
Sander Verdonschot

In this paper we study local routing strategies on geometric graphs. Such strategies use geometric properties of the graph like the coordinates of the current and target nodes to route. Specifically, we study routing strategies in the presence of constraints which are obstacles that edges of the graph are not allowed to cross. Let P be a set of n points in the plane and let S be a set of line segments whose endpoints are in P, with no two line segments intersecting properly. We present the first deterministic 1-local O ( 1 ) -memory routing algorithm that is guaranteed to find a path between two vertices in the visibility graph of P with respect to a set of constraints S. The strategy never looks beyond the direct neighbors of the current node and does not store more than O ( 1 ) -information to reach the target. We then turn our attention to finding competitive routing strategies. We show that when routing on any triangulation T of P such that S ⊆ T, no o ( n ) -competitive routing algorithm exists when the routing strategy restricts its attention to the triangles intersected by the line segment from the source to the target (a technique commonly used in the unconstrained setting). Finally, we provide an O ( n ) -competitive deterministic 1-local O ( 1 ) -memory routing algorithm on any such T, which is optimal in the worst case, given the lower bound.

Details DOI

ICRA Conference 2021 Conference Paper

Robot Development and Path Planning for Indoor Ultraviolet Light Disinfection

Jonathan Conroy
Christopher Thierauf
Parker Rule
Evan A. Krause
Hugo A. Akitaya
Andrei Gonczi
Matias Korman
Matthias Scheutz

Regular irradiation of indoor environments with ultraviolet C (UVC) light has become a regular task for many in-door settings as a result of COVID-19, but current robotic systems attempting to automate it suffer from high costs and inefficient irradiation. In this paper, we propose a purpose-made inexpensive robotic platform with off-the-shelf components and standard navigation software that, with a novel algorithm for finding optimal irradiation locations, addresses both shortcomings to offer affordable and efficient solutions for UVC irradiation. We demonstrate in simulations the efficacy of the algorithm and show a prototypical run of the autonomous integrated robotic system in an indoor environment. In our sample instances, our proposed algorithm reduces the time needed by roughly 30% while it increases the coverage by a factor of 35% (when compared to the best possible placement of a static light).

Details

TCS Journal 2018 Journal Article

Gap-planar graphs

Sang Won Bae
Jean-Francois Baffier
Jinhee Chun
Peter Eades
Kord Eickmeyer
Luca Grilli
Seok-Hee Hong
Matias Korman

We introduce the family of k-gap-planar graphs for k ≥ 0, i. e. , graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition is motivated by applications in edge casing, as a k-gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k-gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k-gap-planar complete graphs, and the computational complexity of recognizing k-gap-planar graphs.

Details DOI

TCS Journal 2017 Journal Article

Hanabi is NP-hard, even for cheaters who look at their cards

Jean-François Baffier
Man-Kwun Chiu
Yago Diez
Matias Korman
Valia Mitsou
André van Renssen
Marcel Roeloffzen
Yushi Uno

In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among c colors and a number between 1 and n. The aim is to make, for each color, a pile of cards of that color with all increasing numbers from 1 to n. At each time during the game, each player holds h cards in hand. Cards are drawn sequentially from a deck and the players should decide whether to play, discard or store them for future use. One of the features of the game is that the players can see their partners' cards but not their own and information must be shared through hints. We introduce a single-player, perfect-information model and show that the game is intractable even for this simplified version where we forego both the hidden information and the multiplayer aspect of the game, even when the player can only hold two cards in her hand. On the positive side, we show that the decision version of the problem—to decide whether or not numbers from 1 through n can be played for every color—can be solved in (almost) linear time for some restricted cases.

Details DOI