Author name cluster

Fabrizio Montecchiani

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.

21 papers

2 author rows

TCS Journal 2026 Journal Article

Partial temporal vertex cover with bounded activity intervals

Riccardo Dondi
Fabrizio Montecchiani
Giacomo Ortali
Tommaso Piselli
Alessandra Tappini

Different variants of Vertex Cover have recently garnered attention in the context of temporal graphs. One of these variants is motivated by the need to summarize timeline activities in social networks. Here, the activities of individual vertices, representing users, are characterized by time intervals. In this paper, we explore a scenario where the temporal span of each vertex’s activity interval is bounded by an integer ℓ, and the objective is to maximize the number of (temporal) edges that are covered. We establish the APX-hardness of this problem and the NP-hardness of the corresponding decision problem, even under the restricted conditions where: the temporal domain comprises only two timestamps and each edge appears at most once and; no two edges are associated to a same label. Subsequently, we delve into the parameterized complexity of the problem, offering two fixed-parameter algorithms parameterized by: (i) the number k of temporal edges covered by the solution, and (ii) the number h of temporal edges not covered by the solution. Finally, we present a polynomial-time approximation algorithm achieving a factor of 3 4.

TCS Journal 2025 Journal Article

Drawing graphs with k vertices per face: Complexity and algorithms

Michael A. Bekos
Giuseppe Di Battista
Emilio Di Giacomo
Walter Didimo
Michael Kaufmann
Fabrizio Montecchiani

A drawing Γ of a graph G divides the plane into topologically connected regions, called faces (or cells). The boundary of each face is formed by vertices, crossings, and edge portions. Given a positive integer k, we say that Γ is a k + -real face drawing of G if the boundary of each face of Γ contains at least k vertices of G. Graphs that admit a k + -real face drawing are k + -real face graphs; they have been studied so far in terms of edge density and inclusion relationships with other notable classes of nonplanar graphs that can be drawn avoiding specific crossing configurations. In this paper, we investigate the complexity of recognizing k + -real face graphs, that is, the complexity of testing whether a given graph is k + -real face, for desired values of k. We study both the general unconstrained scenario and the 2-layer scenario in which the graph is bipartite, the vertices of the two partition sets lie on two distinct horizontal layers, and the edges are drawn as straight-line segments. While we prove NP-completeness results for the unconstrained scenario, we describe efficient recognition algorithms for the 2-layer setting.

AIJ Journal 2025 Journal Article

The influence of dimensions on the complexity of computing decision trees

Stephen Kobourov
Maarten Löffler
Fabrizio Montecchiani
Marcin Pilipczuk
Ignaz Rutter
Raimund Seidel
Manuel Sorge
Jules Wulms

A decision tree recursively splits a feature space $\mathbb{R}^{d}$ and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work treats heuristic algorithms to compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number $d$ of dimensions of the feature space. We show that it can be solved in $O(n^{2d + 1}d)$ time, but under reasonable complexity-theoretic assumptions it is not possible to achieve $f(d) \cdot n^{o(d / \log d)}$ running time, where $n$ is the number of training examples. The problem is solvable in $(dR)^{O(dR)} \cdot n^{1+o(1)}$ time, if there are exactly two classes and $R$ is an upper bound on the number of tree leaves labeled with the first~class.

TCS Journal 2024 Journal Article

Convex grid drawings of planar graphs with constant edge-vertex resolution

Michael A. Bekos
Martin Gronemann
Fabrizio Montecchiani
Antonios Symvonis

In this work, we continue the study of the area required for convex straight-line grid drawings of 3-connected plane graphs, which has been intensively investigated in the last decades. Motivated by applications, such as graph editors, we additionally require the obtained drawings to have bounded edge-vertex resolution, that is, the closest distance between a vertex and any non-incident edge in the drawing is lower bounded by a constant that does not depend on the size of the graph. We present a drawing algorithm that takes as input a 3-connected plane graph with n vertices and f internal faces, and computes a convex straight-line drawing with edge-vertex resolution at least 1 2 on an integer grid of size ( n − 2 + a ) × ( n − 2 + a ), where a = min ⁡ { n − 3, f }. Our result improves the previously best-known area bound of ( 3 n − 7 ) × ( 3 n − 7 ) / 2 by Chrobak, Goodrich and Tamassia.

MFCS Conference 2023 Conference Paper

On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges

Carla Binucci
Giuseppe Liotta
Fabrizio Montecchiani
Giacomo Ortali
Tommaso Piselli

Orienting the edges of an undirected graph such that the resulting digraph satisfies some given constraints is a classical problem in graph theory, with multiple algorithmic applications. In particular, an st-orientation orients each edge of the input graph such that the resulting digraph is acyclic, and it contains a single source s and a single sink t. Computing an st-orientation of a graph can be done efficiently, and it finds notable applications in graph algorithms and in particular in graph drawing. On the other hand, finding an st-orientation with at most k transitive edges is more challenging and it was recently proven to be NP-hard already when k = 0. We strengthen this result by showing that the problem remains NP-hard even for graphs of bounded diameter, and for graphs of bounded vertex degree. These computational lower bounds naturally raise the question about which structural parameters can lead to tractable parameterizations of the problem. Our main result is a fixed-parameter tractable algorithm parameterized by treewidth.

TCS Journal 2023 Journal Article

On the parameterized complexity of s-club cluster deletion problems

Fabrizio Montecchiani
Giacomo Ortali
Tommaso Piselli
Alessandra Tappini

We study the parameterized complexity of the s -Club Cluster Edge Deletion (s -Club Cluster Vertex Deletion) problem: Given a graph G and two integers s ≥ 2 and k ≥ 1, is it possible to remove at most k edges (vertices) from G such that each connected component of the resulting graph has diameter at most s? Both s -Club Cluster Edge Deletion and s -Club Cluster Vertex Deletion problems are known to be NP-hard already when s = 2. We prove that they admit a fixed-parameter tractable algorithm when parameterized by s and the treewidth of the input graph. The proof is based on a unified algorithm that solves the more general problem in which both edges and vertices can be removed from the input graph to obtain a set of disjoint components with bounded diameter. Our approach can also be exploited to solve a related problem, namely s -Club Cover, which asks whether it is possible to cover the vertices of a graph with at most d different s-clubs, for some fixed d ≥ 1 and s ≥ 2.

AAAI Conference 2023 Conference Paper

The Influence of Dimensions on the Complexity of Computing Decision Trees

Stephen G. Kobourov
Maarten Löffler
Fabrizio Montecchiani
Marcin Pilipczuk
Ignaz Rutter
Raimund Seidel
Manuel Sorge
Jules Wulms

A decision tree recursively splits a feature space \mathbb{R}^d and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space \mathbb{R}^d, which contains n training examples. We show that it can be solved in O(n^(2d + 1)) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d) * n^o(d / log d) running time. The problem is solvable in (dR)^O(dR) * n^(1+o(1)) time, if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

PDF Details DOI

TCS Journal 2022 Journal Article

Crossing numbers of beyond-planar graphs

Markus Chimani
Philipp Kindermann
Fabrizio Montecchiani
Pavel Valtr

We study the 1-planar, quasi-planar, and fan-planar crossing number in comparison to the (unrestricted) crossing number of graphs. We prove that there are n-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has Ω ( n ) crossings, while O ( 1 ) crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.

TCS Journal 2021 Journal Article

Ortho-polygon visibility representations of 3-connected 1-plane graphs

Giuseppe Liotta
Fabrizio Montecchiani
Alessandra Tappini

An ortho-polygon visibility representation (OPVR) of an embedded graph G is an embedding-preserving drawing that maps each vertex of G to a distinct orthogonal polygon and each edge of G to a vertical or horizontal visibility between its end-vertices. An OPVR Γ has vertex complexity k if every polygon of Γ has at most k reflex corners. A 1-plane graph is an embedded graph such that each edge is crossed at most once. It is known that 3-connected 1-plane graphs admit an OPVR with vertex complexity at most 12, while vertex complexity at least 2 may be required in some cases. In this paper, we reduce this gap by showing that vertex complexity 5 is always sufficient, while vertex complexity 4 may be sometimes required. These results are based on the study of the combinatorial properties of the B-, T-, and W-configurations in 3-connected 1-plane graphs. An implication of the upper bound is the existence of a O ˜ ( n 10 7 ) -time drawing algorithm that computes an OPVR of an n-vertex 3-connected 1-plane graph on an integer grid of size O ( n ) × O ( n ) and with vertex complexity at most 5.

MFCS Conference 2020 Conference Paper

Layered Fan-Planar Graph Drawings

Therese C. Biedl
Steven Chaplick
Michael Kaufmann 0001
Fabrizio Montecchiani
Martin Nöllenburg
Chrysanthi N. Raftopoulou

In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. In this paper, we study fan-planar drawings that use h (horizontal) 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 the 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 drawing; in particular we bound their pathwidth and show that they have a bar-1-visibility representation.

TCS Journal 2020 Journal Article

Polyline drawings with topological constraints

Emilio Di Giacomo
Peter Eades
Giuseppe Liotta
Henk Meijer
Fabrizio Montecchiani

We study the problem of representing topological graphs as polyline drawings with few bends per edge and such that the topology of the graph is either fully or partially preserved. More formally, let G be a simple topological graph and let Γ be a polyline drawing of G. Drawing Γ partially preserves the topology of G if it has the same external boundary, the same circular order of the edges around each vertex, and the same set of crossings as G, while it fully preserves the topology of G if the planarization of G and the planarization of Γ have the same planar embedding. We prove that if the set of crossing-free edges of G forms a biconnected (connected) spanning subgraph, then G admits a polyline drawing that partially preserves its topology and that has curve complexity at most one (three), i. e. , with at most one (three) bend(s) per edge. If, however, the set of crossing-free edges of G is not a connected spanning subgraph, the curve complexity may be Ω ( n ), while it is O ( 1 ) if the number of connected components is O ( 1 ). Concerning drawings that fully preserve the topology, we show that if G is k-skew (i. e. , it becomes planar after removing k suitably chosen edges), it admits one such drawing with curve complexity at most 2k; for 1-skew graphs, the curve complexity can be reduced to one, which is a tight bound. We also consider optimal 2-plane graphs (i. e. , with at most two crossings per edge and maximum edge density), for which we discuss trade-offs between curve complexity and crossing angle resolution of drawings that fully preserve the topology.

TCS Journal 2019 Journal Article

On 3D visibility representations of graphs with few crossings per edge

Patrizio Angelini
Michael A. Bekos
Michael Kaufmann
Fabrizio Montecchiani

A graph is k-planar if it can be drawn in the plane such that each edge is crossed at most k > 0 times. These graphs represent a natural extension of planar graphs and they are among the most investigated families in the growing field of graph drawing beyond planarity. In this paper, we study visibility representations of k-planar graphs in three dimensions. In particular, we provide a technique for a meaningful family of 2-planar graphs, called 5-kite-augmented graphs, which include as subgraphs all 1-planar graphs and all simple optimal 2-planar graphs (i. e. , those 2-planar graphs that attain the maximum number of edges). We prove that every 5-kite-augmented graph has a z-parallel visibility representation, i. e. , a three-dimensional visibility representation in which the vertices are isothetic disjoint rectangles parallel to the xy-plane, and the edges are unobstructed z-parallel visibilities between pairs of rectangles. In addition, the constructed representation is such that there is a plane that intersects all the rectangles, and this intersection defines a bar 1-visibility representation of the input graph, which is a well-known type of visibility representation in two dimensions.

STOC Conference 2019 Conference Paper

Planar graphs of bounded degree have bounded queue number

Michael A. Bekos
Henry Förster
Martin Gronemann
Tamara Mchedlidze
Fabrizio Montecchiani
Chrysanthi N. Raftopoulou
Torsten Ueckerdt

A queue layout of a graph consists of a linear order of its vertices and a partition of its edges into queues, so that no two independent edges of the same queue are nested. The queue number of a graph is the minimum number of queues required by any of its queue layouts. A long-standing conjecture by Heath, Leighton and Rosenberg states that the queue number of planar graphs is bounded.This conjecture has been partially settled in the positive for several sub- families of planar graphs (most of which have bounded treewidth). In this paper, we make a further important step towards settling this conjecture. We prove that planar graphs of bounded degree (which may have unbounded treewidth) have bounded queue number. A notable implication of this result is that every planar graph of bounded degree admits a three-dimensional straight-line grid drawing in linear volume. Further implications are that every planar graph of bounded degree has bounded track number, and that every k-planar graph (i.e., every graph that can be drawn in the plane with at most k crossings per edge) of bounded degree as bounded queue number.

TCS Journal 2018 Journal Article

Drawing subcubic planar graphs with four slopes and optimal angular resolution

Emilio Di Giacomo
Giuseppe Liotta
Fabrizio Montecchiani

A subcubic planar graph is a planar graph whose vertices have degree at most 3. We show that the subcubic planar graphs with at least five vertices have planar slope number at most 4, which is worst-case optimal. This answers an open question by Jelínek et al. [10]. Furthermore, we prove that the subcubic planar graphs with at least five vertices have angular resolution π / 4, which solves an open problem by Kant [11] and by Formann et al. [8].

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.

TCS Journal 2018 Journal Article

New results on edge partitions of 1-plane graphs

Emilio Di Giacomo
Walter Didimo
William S. Evans
Giuseppe Liotta
Henk Meijer
Fabrizio Montecchiani
Stephen K. Wismath

A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A NIC-plane graph is a 1-plane graph such that any two pairs of crossing edges share at most one end-vertex. An edge partition of a 1-plane graph G is a coloring of the edges of G with two colors, red and blue, such that both the graph induced by the red edges and the graph induced by the blue edges are plane graphs. We prove the following: (i) Every NIC-plane graph admits an edge partition such that the red graph has maximum vertex degree three; this bound on the vertex degree is worst-case optimal. (ii) Deciding whether a NIC-plane graph admits an edge partition such that the red graph has maximum vertex degree two is NP-complete. (iii) Deciding whether a 1-plane graph admits an edge partition such that the red graph has maximum vertex degree one, and computing one in the positive case, can be done in quadratic time. Applications of these results to graph drawing are also discussed.

TCS Journal 2017 Journal Article

On partitioning the edges of 1-plane graphs

William J. Lenhart
Giuseppe Liotta
Fabrizio Montecchiani

A 1-plane graph is a graph embedded in the plane such that each edge is crossed at most once. A 1-plane graph is optimal if it has maximum edge density. A red–blue edge coloring of an optimal 1-plane graph G partitions the edge set of G into blue edges and red edges such that no two blue edges cross each other and no two red edges cross each other. We prove the following: (i) Every optimal 1-plane graph has a red–blue edge coloring such that the blue subgraph is maximal planar while the red subgraph has vertex degree at most four; this bound on the vertex degree is worst-case optimal. (ii) A red–blue edge coloring may not always induce a red forest of bounded vertex degree. Applications of these results to graph augmentation and graph drawing are also discussed.

TCS Journal 2017 Journal Article

On RAC drawings of 1-planar graphs

Michael A. Bekos
Walter Didimo
Giuseppe Liotta
Saeed Mehrabi
Fabrizio Montecchiani

A drawing of a graph is 1-planar if each edge is crossed at most once. A graph is 1-planar if it has a 1-planar drawing. A k-bend RAC (Right Angle Crossing) drawing of a graph is a polyline drawing where each edge has at most k bends and edges cross only at right angles. A graph is k-bend RAC if it has a k-bend RAC drawing. A 0-bend RAC graph (drawing) is also called a straight-line RAC graph (drawing). The relationships between 1-planar and k-bend RAC graphs have been partially studied in the literature. It is known that there are both 1-planar graphs that are not straight-line RAC and straight-line RAC graphs that are not 1-planar. The existence of 1-planar straight-line RAC drawings has been proven only for restricted families of 1-planar graphs. Two of the main questions still open are: (i) What is the complexity of deciding whether a graph has a drawing that is both 1-planar and straight-line RAC? ( i i ) Does every 1-planar graph have a drawing that is both 1-planar and 1-bend RAC? In this paper we answer these two questions. Namely, we prove an NP-hardness result for the first question, and we positively answer the second question by describing a drawing algorithm for 1-planar graphs.

TCS Journal 2016 Journal Article

Recognizing and drawing IC-planar graphs

Franz J. Brandenburg
Walter Didimo
William S. Evans
Philipp Kindermann
Giuseppe Liotta
Fabrizio Montecchiani

We give new results about the relationship between 1-planar graphs and RAC graphs. A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph is RAC if it can be drawn in such a way that its edges cross only at right angles. These two classes of graphs and their relationships have been widely investigated in the last years, due to their relevance in application domains where computing readable graph layouts is important to analyze or design relational data sets. We study IC-planar graphs, the sub-family of 1-planar graphs that admit 1-planar drawings with independent crossings (i. e. , no two crossed edges share an endpoint). We prove that every IC-planar graph admits a straight-line RAC drawing, which may require however exponential area. If we do not require right angle crossings, we can draw every IC-planar graph with straight-line edges in linear time and quadratic area. We then study the problem of testing whether a graph is IC-planar. We prove that this problem is NP-hard, even if a rotation system for the graph is fixed. On the positive side, we describe a polynomial-time algorithm that tests whether a triangulated plane graph augmented with a given set of edges that form a matching is IC-planar.

TCS Journal 2016 Journal Article

Simultaneous visibility representations of plane st-graphs using L-shapes

William S. Evans
Giuseppe Liotta
Fabrizio Montecchiani

Let 〈 G r, G b 〉 be a pair of plane st-graphs with the same vertex set V. A simultaneous visibility representation with L-shapes of 〈 G r, G b 〉 is a pair of bar visibility representations 〈 Γ r, Γ b 〉 such that, for every vertex v ∈ V, Γ r ( v ) and Γ b ( v ) are a horizontal and a vertical segment, respectively, which share an end-point. In other words, every vertex is drawn as an L-shape, every edge of G r is a vertical visibility segment, and every edge of G b is a horizontal visibility segment. Also, no two L-shapes intersect each other. An L-shape has four possible rotations, and we assume that each vertex is given a rotation for its L-shape as part of the input. Our main results are: (i) a characterization of those pairs of plane st-graphs admitting such a representation, (ii) a quadratic time algorithm to recognize them, and (iii) a linear time drawing algorithm if the test is positive. As an application, starting from a simultaneous visibility representation with L-shapes, we show how to compute a simultaneous embedding of the two graphs with at most two bends per edge and right-angle crossings.

TCS Journal 2015 Journal Article

Fan-planarity: Properties and complexity

Carla Binucci
Emilio Di Giacomo
Walter Didimo
Fabrizio Montecchiani
Maurizio Patrignani
Antonios Symvonis
Ioannis G. Tollis

In a fan-planar drawing of a graph an edge can cross only edges with a common end-vertex. Fan-planar drawings have been recently introduced by Kaufmann and Ueckerdt [35], who proved that every n-vertex fan-planar drawing has at most 5 n − 10 edges, and that this bound is tight for n ≥ 20. We extend their result from both the combinatorial and the algorithmic point of view. We prove tight bounds on the density of constrained versions of fan-planar drawings and study the relationship between fan-planarity and k-planarity. Also, we prove that testing fan-planarity in the variable embedding setting is NP-complete.