Search results for: Emilio Di Giacomo

Items from 1 to 20 out of 28 results

article

NodeTrix Planarity Testing with Small Clusters

Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani, Ignaz Rutter, more

Algorithmica > 2019 > 81 > 9 > 3464-3493

We study the NodeTrix planarity testing problem for flat clustered graphs when the maximum size of each cluster is bounded by a constant k. We consider both the case when the sides of the matrices to which the edges are incident are fixed and the case when they can be chosen arbitrarily. We show that NodeTrix planarity testing with fixed sides can be solved in $$O(k^{3k+\frac{3}{2}} \cdot n)$$...

article

1 -page and 2 -page drawings with bounded number of crossings per edge

Carla Binucci, Emilio Di Giacomo, Md. Iqbal Hossain, Giuseppe Liotta

European Journal of Combinatorics > 2018 > 68 > C > 24-37

A drawing of a graph such that the vertices are drawn as points along a line and each edge is a circular arc in one of the two half-planes defined by this line is called a 2 -page drawing. If all edges are in the same half-plane, the drawing is called a 1 -page drawing. We want to compute 1 -page and 2 -page drawings of planar graphs such that the number of crossings per edge does not depend on...

article

Designing the Content Analyzer of a Travel Recommender System

Carla Binucci, Felice De Luca, Emilio Di Giacomo, Giuseppe Liotta, more

Expert Systems with Applications > 2017 > 87 > C > 199-208

Content-based travel recommender systems suggest touristic attractions based on a best match between users’ preferences and a given set of points of interests, called POIs for short. When designing such systems, a critical aspect is to equip them with a rich enough knowledge base that, for each POI, indicates how much the POI is relevant for a set of possible topics of interests, also called TOIs...

chapter

An interactive system for exhibitions in a science and technology center

Alessio De Angelis, Paolo Carbone, Marco Dionigi, Emilio Di Giacomo, more

2017 IEEE International Systems Engineering Symposium (ISSE) > 1 - 6

2017 IEEE International Systems Engineering Symposium (ISSE)

This paper presents the development of a system for realizing interactive exhibitions in the context of a science and technology center. The core functionality of the system is provided by a positioning subsystem comprised of a fixed infrastructure of transmitters and a sensor worn by a user. The operating principle of the positioning system is based on inductive coupling of resonators. Information...

article

Ortho-polygon Visibility Representations of Embedded Graphs

Emilio Di Giacomo, Walter Didimo, William S. Evans, Giuseppe Liotta, more

Algorithmica > 2018 > 80 > 8 > 2345-2383

An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms...

article

Lower and upper bounds for long induced paths in 3-connected planar graphs

Emilio Di Giacomo, Giuseppe Liotta, Tamara Mchedlidze

Theoretical Computer Science > 2016 > 636 > C > 47-55

Let G be a 3-connected planar graph with n vertices and let p(G) be the maximum number of vertices of an induced subgraph of G that is a path. Substantially improving previous results, we prove that p(G)≥log⁡n12log⁡log⁡n. To demonstrate the tightness of this bound, we notice that the above inequality implies p(G)∈Ω((log2⁡n)1−ε), where ε is any positive constant smaller than 1, and describe an infinite...

chapter

Network visualization retargeting

Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani

2015 6th International Conference on Information, Intelligence, Systems and Applications (IISA) > 1 - 6

2015 6th International Conference on Information, Intelligence, Systems and Applications (IISA)

The impressive and pervasive growth of different mobile devices allows people to quickly access and share a large variety of multimedia contents. These devices offer a heterogeneous set of display capabilities, with several types of resolution levels and screen sizes. This scenario often requires to adapt the displayed images to the aspect ratio of the different screens, without loosing salient visual...

chapter

Low ply graph drawing

Emilio Di Giacomo, Walter Didimo, Seok-hee Hong, Michael Kaufmann, more

2015 6th International Conference on Information, Intelligence, Systems and Applications (IISA) > 1 - 6

2015 6th International Conference on Information, Intelligence, Systems and Applications (IISA)

We consider the problem of characterizing graphs with low ply number and algorithms for creating layouts of graphs with low ply number. Informally, the ply number of a straight-line drawing of a graph is defined as the maximum number of overlapping disks, where each disk is associated with a vertex and has a radius that is half the length of the longest edge incident to that vertex. We show that internally...

chapter

VisFLOWer: Visual analysis of touristic flows

Carla Binucci, Felice De Luca, Emilio Di Giacomo, Giuseppe Liotta, more

2015 6th International Conference on Information, Intelligence, Systems and Applications (IISA) > 1 - 6

2015 6th International Conference on Information, Intelligence, Systems and Applications (IISA)

Touristic data represent a valuable and useful source of knowledge for local administrators. Using visualization systems helps them in understanding the main trends of touristic flows directed to the different attractions of their territory and thus it supports their decision making processes. In fact, the problem of visualizing flows of people (or other entities) between geographical places has recently...

article

The Approximate Rectangle of Influence Drawability Problem

Emilio Di Giacomo, Giuseppe Liotta, Henk Meijer

Algorithmica > 2015 > 72 > 2 > 620-655

Let ε ₁,ε ₂ be two non negative numbers. An approximate rectangle of influence drawing (also called (ε ₁,ε ₂)-RID) is a proximity drawing of a graph such that: (i) if u,v are adjacent vertices then their rectangle of influence “scaled down” by the factor $\frac{1}{1+\varepsilon_{1}}$ does not contain other vertices of the drawing; (ii) if u,v are not adjacent, then their rectangle of influence...

article

Techniques for Edge Stratification of Complex Graph Drawings

Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani, more

Journal of Visual Languages and Computing > 2014 > 25 > 4 > 533-543

We propose an approach that allows a user (e.g., an analyst) to explore a layout produced by any graph drawing algorithm, in order to reduce the visual complexity and clarify its presentation. Our approach is based on stratifying the drawing into layers with desired properties; to this aim, heuristics are presented. The produced layers can be explored and combined by the user to gradually acquire...

chapter

Upward-rightward planar drawings

Emilio Di Giacomo, Walter Didimo, Michael Kaufmann, Giuseppe Liotta, more

IISA 2014, The 5th International Conference on Information, Intelligence, Systems and Applications > 145 - 150

2014 5th International Conference on Information, Intelligence, Systems and Applications (IISA)

Upward drawing is a widely studied drawing convention for the visual representation of directed graphs. In an upward drawing vertices are mapped to distinct points of the plane, and edges are curves monotonically increasing in the vertical direction, according to their orientation. In particular, not all planar digraphs admit an upward planar drawing (i.e., an upward drawing with no edge crossing),...

article

2-Layer Right Angle Crossing Drawings

Emilio Di Giacomo, Walter Didimo, Peter Eades, Giuseppe Liotta

Algorithmica > 2014 > 68 > 4 > 954-997

A 2-layer drawing represents a bipartite graph where each vertex is a point on one of two parallel lines, no two vertices on the same line are adjacent, and the edges are straight-line segments. In this paper we study 2-layer drawings where any two crossing edges meet at right angle. We characterize the graphs that admit this type of drawing, provide linear-time testing and embedding algorithms, and...

article

Area requirement of graph drawings with few crossings per edge

Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani

Computational Geometry: Theory and Applications > 2013 > 46 > 8 > 909-916

In this paper we study how to compute compact straight-line drawings of planar graphs with a limited number of crossings per edge. We prove that every outerplanar graph can be drawn in O(nlogn) area using a sub-linear number of crossings per edge, and that for any given number ε>0, every outerplanar graph admits an O(n1+ε) area drawing with O(n1−ε) crossing per edge. The drawing algorithms run...

article

Orthogeodesic point-set embedding of trees

Emilio Di Giacomo, Fabrizio Frati, Radoslav Fulek, Luca Grilli, more

Computational Geometry: Theory and Applications > 2013 > 46 > 8 > 929-944

Let S be a set of N grid points in the plane, no two of which lie on the same horizontal or vertical line, and let G be a graph with n vertices (n⩽N). An orthogeodesic point-set embedding of G on S is a drawing of G such that each vertex is drawn as a point of S and each edge is a chain of horizontal and vertical segments with bends on grid points whose length is equal to the Manhattan distance of...

article

Hamiltonian orthogeodesic alternating paths

Emilio Di Giacomo, Luca Grilli, Marcus Krug, Giuseppe Liotta, more

Journal of Discrete Algorithms > 2012 > 16 > Complete > 34-52

Let R be a set of red points and let B be a set of blue points. The point set P=R∪B is called equitable if ||B|−|R||⩽1 and it is called general if no two points are vertically or horizontally aligned. An orthogeodesic alternating path on P is a path such that each edge is an orthogeodesic chain connecting points of different color and such that no two edges cross. We consider the problem of deciding...

article

Drawing a tree as a minimum spanning tree approximation

Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer

Journal of Computer and System Sciences > 2012 > 78 > 2 > 491-503

We introduce and study (1+ε)-EMST drawings, i.e., planar straight-line drawings of trees such that, for any fixed ε>0, the distance between any two vertices is at least 11+ε the length of the longest edge in the path connecting them. (1+ε)-EMST drawings are good approximations of Euclidean minimum spanning trees. While it is known that only trees with bounded degree have a Euclidean minimum spanning...

article

Bounds on the crossing resolution of complete geometric graphs

Emilio Di Giacomo, Walter Didimo, Peter Eades, Seok-Hee Hong, more

Discrete Applied Mathematics > 2012 > 160 > 1-2 > 132-139

The crossing resolution of a geometric graph is the minimum crossing angle at which any two edges cross each other. In this paper, we present upper and lower bounds to the crossing resolution of the complete geometric graphs.

article

Upward straight-line embeddings of directed graphs into point sets

Carla Binucci, Emilio Di Giacomo, Walter Didimo, Alejandro Estrella-Balderrama, more

Computational Geometry: Theory and Applications > 2010 > 43 > 2 > 219-232

In this paper we study the problem of computing an upward straight-line embedding of a planar DAG (directed acyclic graph) G into a point set S, i.e. a planar drawing of G such that each vertex is mapped to a point of S, each edge is drawn as a straight-line segment, and all the edges are oriented according to a common direction. In particular, we show that no biconnected DAG admits an upward straight-line...

article

Point-set embeddings of trees with given partial drawings

Emilio Di Giacomo, Walter Didimo, Giuseppe Liotta, Henk Meijer, more

Computational Geometry: Theory and Applications > 2009 > 42 > 6-7 > 664-676

Given a graph G with n vertices and a set S of n points in the plane, a point-set embedding of G on S is a planar drawing such that each vertex of G is mapped to a distinct point of S. A geometric point-set embedding is a point-set embedding with no edge bends. This paper studies the following problem: The input is a set S of n points, a planar graph G with n vertices, and a geometric point-set embedding...

Publication date

Set your own date range

INFONA - science communication portal

Search results for: Emilio Di Giacomo

NodeTrix Planarity Testing with Small Clusters

1 -page and 2 -page drawings with bounded number of crossings per edge

Designing the Content Analyzer of a Travel Recommender System

An interactive system for exhibitions in a science and technology center

Ortho-polygon Visibility Representations of Embedded Graphs

Lower and upper bounds for long induced paths in 3-connected planar graphs

Network visualization retargeting

Low ply graph drawing

VisFLOWer: Visual analysis of touristic flows

The Approximate Rectangle of Influence Drawability Problem

Techniques for Edge Stratification of Complex Graph Drawings

Upward-rightward planar drawings

2-Layer Right Angle Crossing Drawings

Area requirement of graph drawings with few crossings per edge

Orthogeodesic point-set embedding of trees

Hamiltonian orthogeodesic alternating paths

Drawing a tree as a minimum spanning tree approximation

Bounds on the crossing resolution of complete geometric graphs

Upward straight-line embeddings of directed graphs into point sets

Point-set embeddings of trees with given partial drawings

Filter options

Publication date

Publication type

Keywords

Data set

Journal

INFONA - science communication portal

Search results for: Emilio Di Giacomo

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Publication type

Keywords

Data set

Journal

Reporting an error / abuse

Sending the report failed

Accessibility options