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

Daniel Gonçalves

Daniel Gonçalves appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OAmath.COmath.DSmath.RADiscrete MathematicsData Structures and AlgorithmsComputational GeometryComputational ComplexityHuman-Computer Interactionmath.GNmath.PR

Catalog footprint

What is connected

39works
11topics
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

39 published item(s)

preprint2026arXiv

Pushing the frontiers of subexponential FPT time for Feedback Vertex Set

The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph $G$ and a parameter $k$, one has to decide if there is a set $S$ of at most $k$ vertices such that $G-S$ is acyclic. Assuming the Exponential Time Hypothesis, it is known that FVS cannot be solved in time $2^{o(k)}n^{\mathcal{O}(1)}$ in general graphs. To overcome this, many recent results considered FVS restricted to particular intersection graph classes and provided such $2^{o(k)}n^{\mathcal{O}(1)}$ algorithms. In this paper we provide generic conditions on a graph class for the existence of an algorithm solving FVS in subexponential FPT time, i.e. time $2^{k^\varepsilon} \mathop{\rm poly}(n)$, for some $\varepsilon<1$, where $n$ denotes the number of vertices of the instance and $k$ the parameter. On the one hand this result unifies algorithms that have been proposed over the years for several graph classes such as planar graphs, map graphs, unit-disk graphs, pseudo-disk graphs, and string graphs of bounded edge-degree. On the other hand it extends the tractability horizon of FVS to new classes that are not amenable to previously used techniques, in particular intersection graphs of ``thin'' objects like segment graphs or more generally $s$-string graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

C*-Algebras of one-sided subshifts over arbitrary alphabets

We associate a C*-algebra $\widetilde{\mathcal{O}}_{\textsf{X}}$ with a subshift over an arbitrary, possibly infinite, alphabet. We show that $\widetilde{\mathcal{O}}_{\textsf{X}}$ is a full invariant for topological conjugacy of the subshifts of Ott, Tomforde, and Willis. When the alphabet is countable, we show that $\widetilde{\mathcal{O}}_{\textsf{X}}$ is an invariant for isometric conjugacy of subshifts with the product metric. For a suitable partial action associated with a subshift over a countable alphabet, we show that $\widetilde{\mathcal{O}}_{\textsf{X}}$ is also an invariant for continuous orbit equivalence. Additionally, we give a concrete way to compute the K-theory of $\widetilde{\mathcal{O}}_{\textsf{X}}$ and illustrate it with two examples.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Unifying interval maps and branching systems with applications to relative graph C*-algebras

We describe Markov interval maps via branching systems and develop the theory of relative branching systems, characterizing when the associated representations of relative graph C*-algebras are faithful. When the Markov interval maps $f$ have escape sets, we use our results to characterize injectivity of the associated relative graph algebra representations, improving on previous work by the first, third, and fourth authors.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Irreducibility and monicity for representations of $k$-graph $C^*$-algebras

The representations of a $k$-graph $C^*$-algebra $C^*(Λ)$ which arise from $Λ$-semibranching function systems are closely linked to the dynamics of the $k$-graph $Λ$. In this paper, we undertake a systematic analysis of the question of irreducibility for these representations. We provide a variety of necessary and sufficient conditions for irreducibility, as well as a number of examples indicating the optimality of our results. We also explore the relationship between irreducible $Λ$-semibranching representations and purely atomic representations of $C^*(Λ)$. Throughout the paper, we work in the setting of row-finite source-free $k$-graphs; this paper constitutes the first analysis of $Λ$-semibranching representations at this level of generality.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Chains in evolution algebras

In this work we approach three-dimensional evolution algebras from certain constructions performed on two-dimensional algebras. More precisely, we provide four different constructions producing three-dimensional evolution algebras from two-dimensional algebras. Also we introduce two parameters, the annihilator stabilizing index and the socle stabilizing index, which are useful tools in the classification theory of these algebras. Finally, we use moduli sets as a convenient way to describe isomorphism classes of algebras.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Exploring How Personality Models Information Visualization Preferences

Recent research on information visualization has shown how individual differences act as a mediator on how users interact with visualization systems. We focus our exploratory study on whether personality has an effect on user preferences regarding idioms used for hierarchy, evolution over time, and comparison contexts. Specifically, we leverage all personality variables from the Five-Factor Model and the three dimensions from Locus of Control (LoC) with correlation and clustering approaches. The correlation-based method suggested that Neuroticism, Openness to Experience, Agreeableness, several facets from each trait, and the External dimensions from LoC mediate how much individuals prefer certain idioms. In addition, our results from the cluster-based analysis showed that Neuroticism, Extraversion, Conscientiousness, and all dimensions from LoC have an effect on preferences for idioms in hierarchy and evolution contexts. Our results support the incorporation of in-depth personality synergies with InfoVis into the design pipeline of visualization systems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

KMS states and continuous orbit equivalence for ultragraph shift spaces with sinks

We extend ultragraph shift spaces and the realization of ultragraph C*-algebras as partial crossed products to include ultragraphs with sinks (under a mild condition, called (RFUM2), which allow us to dismiss the use of filters) and we describe the associated transformation groupoid. Using these characterizations we study continuous orbit equivalence of ultragraph shift spaces (via groupoids) and KMS and ground states (via partial crossed products).

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Topological full groups of ultragraph groupoids as an isomorphism invariant

We prove two isomorphism-invariance theorems for groupoids associated with ultragraphs. These theorems characterize ultragraphs for which the topological full group of an associated groupoid is an isomorphism invariant. These results extend those of graph groupoids to ultragraph groupoids while providing another concrete example where the topological full group of a groupoid is a complete isomorphism invariant.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Ultragraph algebras via labelled graph groupoids, with applications to generalized uniqueness theorems

An ultragraph gives rise to a labelled graph with some particular properties. In this paper we describe the algebras associated to such labelled graphs as groupoid algebras. More precisely, we show that the known groupoid algebra realization of ultragraph C*-algebras is only valid for ultragraphs for which the range of each edge is finite, and we extend this realization to any ultragraph (including ultragraphs with sinks). Using our machinery, we characterize the shift space associated to an ultragraph as the tight spectrum of the inverse semigroup associated to the ultragraph (viewed as a labelled graph). Furthermore, in the purely algebraic setting, we show that the algebraic partial action used to describe an ultragraph Leavitt path algebra as a partial skew group ring is equivalent to the dual of a topological partial action, and we use this to describe ultragraph Leavitt path algebras as Steinberg algebras. Finally, we prove generalized uniqueness theorems for both ultragraph C*-algebras and ultragraph Leavitt path algebras and characterize their abelian core subalgebras.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Branching Systems and General Cuntz-Krieger Uniqueness Theorem for Ultragraph C*-algebras

We give a notion of branching systems on ultragraphs. From this we build concrete representations of ultragraph C*-algebras on the bounded linear operators of Hilbert spaces. To each branching system of an ultragraph we describe the associated Perron-Frobenius operator in terms of the induced representation. We show that every permutative representation of an ultragraph C*-algebra is unitary equivalent to a representation arising from a branching system. We give a sufficient condition on ultragraphs such that a large class of representations of the C*-algebras of these ultragraphs is permutative. To give a sufficient condition on branching systems so that their induced representations are faithful we generalize Szyma{ń}ski's version of the Cuntz-Krieger uniqueness theorem for ultragraph C*-algebras.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Coloring non-crossing strings

For a family of geometric objects in the plane $\mathcal{F}=\{S_1,\ldots,S_n\}$, define $χ(\mathcal{F})$ as the least integer $\ell$ such that the elements of $\mathcal{F}$ can be colored with $\ell$ colors, in such a way that any two intersecting objects have distinct colors. When $\mathcal{F}$ is a set of pseudo-disks that may only intersect on their boundaries, and such that any point of the plane is contained in at most $k$ pseudo-disks, it can be proven that $χ(\mathcal{F})\le 3k/2 + o(k)$ since the problem is equivalent to cyclic coloring of plane graphs. In this paper, we study the same problem when pseudo-disks are replaced by a family $\mathcal{F}$ of pseudo-segments (a.k.a. strings) that do not cross. In other words, any two strings of $\mathcal{F}$ are only allowed to "touch" each other. Such a family is said to be $k$-touching if no point of the plane is contained in more than $k$ elements of $\mathcal{F}$. We give bounds on $χ(\mathcal{F})$ as a function of $k$, and in particular we show that $k$-touching segments can be colored with $k+5$ colors. This partially answers a question of Hliněný (1998) on the chromatic number of contact systems of strings.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the structure of Schnyder woods on orientable surfaces

We propose a simple generalization of Schnyder woods from the plane to maps on orientable surfaces of higher genus. This is done in the language of angle labelings. Generalizing results of De Fraysseix and Ossona de Mendez, and Felsner, we establish a correspondence between these labelings and orientations and characterize the set of orientations of a map that correspond to such a Schnyder labeling. Furthermore, we study the set of these orientations of a given map and provide a natural partition into distributive lattices depending on the surface homology. This generalizes earlier results of Felsner and Ossona de Mendez. In the toroidal case, a new proof for the existence of Schnyder woods is derived from this approach.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Encoding toroidal triangulations

Poulalhon and Schaeffer introduced an elegant method to linearly encode a planar triangulation optimally. The method is based on performing a special depth-first search algorithm on a particular orientation of the triangulation: the minimal Schnyder wood. Recent progress toward generalizing Schnyder woods to higher genus enables us to generalize this method to the toroidal case. In the plane, the method leads to a bijection between planar triangulations and some particular trees. For the torus we obtain a similar bijection but with particular unicellular maps (maps with only one face).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Entropy compression method applied to graph colorings

Based on the algorithmic proof of Lovász local lemma due to Moser and Tardos, the works of Grytczuk et al. on words, and Dujmović et al. on colorings, Esperet and Parreau developed a framework to prove upper bounds for several chromatic numbers (in particular acyclic chromatic index, star chromatic number and Thue chromatic number) using the so-called \emph{entropy compression method}. Inspired by this work, we propose a more general framework and a better analysis. This leads to improved upper bounds on chromatic numbers and indices. In particular, every graph with maximum degree $Δ$ has an acyclic chromatic number at most $\frac{3}{2}Δ^{\frac43} + O(Δ)$. Also every planar graph with maximum degree $Δ$ has a facial Thue choice number at most $Δ+ O(Δ^\frac 12)$ and facial Thue choice index at most $10$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On independent set on B1-EPG graphs

In this paper we consider the Maximum Independent Set problem (MIS) on $B_1$-EPG graphs. EPG (for Edge intersection graphs of Paths on a Grid) was introduced in ~\cite{edgeintersinglebend} as the class of graphs whose vertices can be represented as simple paths on a rectangular grid so that two vertices are adjacent if and only if the corresponding paths share at least one edge of the underlying grid. The restricted class $B_k$-EPG denotes EPG-graphs where every path has at most $k$ bends. The study of MIS on $B_1$-EPG graphs has been initiated in~\cite{wadsMIS} where authors prove that MIS is NP-complete on $B_1$-EPG graphs, and provide a polynomial $4$-approximation. In this article we study the approximability and the fixed parameter tractability of MIS on $B_1$-EPG. We show that there is no PTAS for MIS on $B_1$-EPG unless P$=$NP, even if there is only one shape of path, and even if each path has its vertical part or its horizontal part of length at most $3$. This is optimal, as we show that if all paths have their horizontal part bounded by a constant, then MIS admits a PTAS. Finally, we show that MIS is FPT in the standard parameterization on $B_1$-EPG restricted to only three shapes of path, and $W_1$-hard on $B_2$-EPG. The status for general $B_1$-EPG (with the four shapes) is left open.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Ultragraphs and shifts spaces over infinite alphabets

In this paper we further develop the theory of one sided shift spaces over infinite alphabets, characterizing one-step shifts as edge shifts of ultragraphs and partially answering a conjecture regarding shifts of finite type (we show that there exists shifts of finite type that are not conjugate, via a conjugacy that is eventually finite periodic, to an edge shift of a graph ). We also show that there exists edge shifts of ultragraphs that are shifts of finite type, but are not conjugate to a full shift, a result that is not true for edge shifts of graphs. One of the key results needed in the proofs of our conclusions is the realization of a class of ultragraph C*-algebras as partial crossed products, a result of interest on its own.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

(M + 1)-step shift spaces that are not conjugate to M-step shift spaces

Recently Ott, Tomforde and Willis proposed a new approach for one sided shift spaces over infinite alphabets. In this new approach the conjugacy classes of shifts of finite type, edge shifts, and M-step shifts are distinct and the authors conjecture that for each non-negative integer M there exist an (M+1)-step shift space that is not conjugate to any M-step shift. In this short paper we build a class of (M+1)-step shifts that are not conjugate to any M-step shift and hence show that their conjecture is correct.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Polynomial-time Algorithm for Outerplanar Diameter Improvement

The Outerplanar Diameter Improvement problem asks, given a graph $G$ and an integer $D$, whether it is possible to add edges to $G$ in a way that the resulting graph is outerplanar and has diameter at most $D$. We provide a dynamic programming algorithm that solves this problem in polynomial time. Outerplanar Diameter Improvement demonstrates several structural analogues to the celebrated and challenging Planar Diameter Improvement problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Branching systems and representations of Cohn-Leavitt path algebras of separated graphs

We construct for each separated graph (E;C) a family of branching systems over a set X and show how each branching system induces a representation of the Cohn-Leavitt path algebra associated to (E;C) as homomorphisms over the module of functions in X. We also prove that the abelianized Cohn-Leavitt path algebra of a separated graph with no loops can be written as an amalgamated free product of abelianized Cohn-Leavitt algebras that can be faithfully represented via branching systems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Graph C*-algebras, branching systems and the Perron-Frobenius operator

In this paper we show how to produce a large number of representations of a graph C*-algebra in the space of the bounded linear operators in $L^2(X,μ)$. These representations are very concrete and, in the case of graphs that satisfy condition (K), we use our techniques to realize the associated graph C*-algebra as a subalgebra of the bounded operators in $L^2(R)$. We also show how to describe some Perron-Frobenius operators in $L^1(X,μ)$, in terms of the representations we associate to a graph.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Two floor building needing eight colors

Motivated by frequency assignment in office blocks, we study the chromatic number of the adjacency graph of $3$-dimensional parallelepiped arrangements. In the case each parallelepiped is within one floor, a direct application of the Four-Colour Theorem yields that the adjacency graph has chromatic number at most $8$. We provide an example of such an arrangement needing exactly $8$ colours. We also discuss bounds on the chromatic number of the adjacency graph of general arrangements of $3$-dimensional parallelepipeds according to geometrical measures of the parallelepipeds (side length, total surface or volume).

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Understanding Individual Differences: Towards Effective Mobile Interface Design and Adaptation for the Blind

No two people are alike. We usually ignore this diversity as we have the capability to adapt and, without noticing, become experts in interfaces that were probably misadjusted to begin with. This adaptation is not always at the user's reach. One neglected group is the blind. Spatial ability, memory, and tactile sensitivity are some characteristics that diverge between users. Regardless, all are presented with the same methods ignoring their capabilities and needs. Interaction with mobile devices is highly visually demanding which widens the gap between blind people. Our research goal is to identify the individual attributes that influence mobile interaction, considering the blind, and match them with mobile interaction modalities in a comprehensive and extensible design space. We aim to provide knowledge both for device design, device prescription and interface adaptation.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Locally identifying coloring in bounded expansion classes of graphs

A proper vertex coloring of a graph is said to be locally identifying if the sets of colors in the closed neighborhood of any two adjacent non-twin vertices are distinct. The lid-chromatic number of a graph is the minimum number of colors used by a locally identifying vertex-coloring. In this paper, we prove that for any graph class of bounded expansion, the lid-chromatic number is bounded. Classes of bounded expansion include minor closed classes of graphs. For these latter classes, we give an alternative proof to show that the lid-chromatic number is bounded. This leads to an explicit upper bound for the lid-chromatic number of planar graphs. This answers in a positive way a question of Esperet et al [L. Esperet, S. Gravier, M. Montassier, P. Ochem and A. Parreau. Locally identifying coloring of graphs. Electronic Journal of Combinatorics, 19(2), 2012.].

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On triangles in K_r-minor free graphs

We study graphs where each edge adjacent to a vertex of small degree (7 and 9, respectively) belongs to many triangles (4 and 5, respectively) and show that these graphs contain a complete graph (K_6 and K_7, respectively) as a minor. The second case settles a problem of Nevo (Nevo, 2007). Morevover if each edge of a graph belongs to 6 triangles then the graph contains a K_8-minor or contains K_{2,2,2,2,2} as an induced subgraph. We then show applications of these structural properties to stress freeness and coloration of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every K_7-minor free graph is 8-colorable and every K_8-minor free graph is 10-colorable.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Partial crossed products as equivalence relation algebras

For a free partial action of a group in a set we realize the associated partial skew group ring as an algebra of functions with finite support over an equivalence relation and we use this result to characterize the ideals in the partial skew group ring. This generalizes, to the purely algebraic setting, the known characterization of partial C*-crossed products as groupoid C*-algebras. For completeness we include a new proof of the C* result for free partial actions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Simplicity of partial skew group rings and maximal commutativity

Let R0 be a commutative associative ring (not necessarily unital), G a group and alpha a partial action by ideals that contain local units. We show that R0 is maximal commutative in the partial skew group ring R0*G if and only if R0 has the ideal intersection property in R0*G. From this we derive a criterion for simplicity of R0*G in terms of maximal commutativity and $G-$simplicity of R0 and apply this to two examples, namely to partial actions by clopen subsets of a compact set and to give a new proof of the simplicity criterion for Leavitt path algebras. A new proof of the Cuntz-Krieger uniqueness theorem for Leavitt path algebras is also provided.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Parameterized Domination in Circle Graphs

A circle graph is the intersection graph of a set of chords in a circle. Keil [Discrete Applied Mathematics, 42(1):51-63, 1993] proved that Dominating Set, Connected Dominating Set, and Total Dominating Set are NP-complete in circle graphs. To the best of our knowledge, nothing was known about the parameterized complexity of these problems in circle graphs. In this paper we prove the following results, which contribute in this direction: - Dominating Set, Independent Dominating Set, Connected Dominating Set, Total Dominating Set, and Acyclic Dominating Set are W[1]-hard in circle graphs, parameterized by the size of the solution. - Whereas both Connected Dominating Set and Acyclic Dominating Set are W[1]-hard in circle graphs, it turns out that Connected Acyclic Dominating Set is polynomial-time solvable in circle graphs. - If T is a given tree, deciding whether a circle graph has a dominating set isomorphic to T is NP-complete when T is in the input, and FPT when parameterized by |V(T)|. We prove that the FPT algorithm is subexponential.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The Maximum Clique Problem in Multiple Interval Graphs

Multiple interval graphs are variants of interval graphs where instead of a single interval, each vertex is assigned a set of intervals on the real line. We study the complexity of the MAXIMUM CLIQUE problem in several classes of multiple interval graphs. The MAXIMUM CLIQUE problem, or the problem of finding the size of the maximum clique, is known to be NP-complete for $t$-interval graphs when $t\geq 3$ and polynomial-time solvable when $t=1$. The problem is also known to be NP-complete in $t$-track graphs when $t\geq 4$ and polynomial-time solvable when $t\leq 2$. We show that MAXIMUM CLIQUE is already NP-complete for unit 2-interval graphs and unit 3-track graphs. Further, we show that the problem is APX-complete for 2-interval graphs, 3-track graphs, unit 3-interval graphs and unit 4-track graphs. We also introduce two new classes of graphs called $t$-circular interval graphs and $t$-circular track graphs and study the complexity of the MAXIMUM CLIQUE problem in them. On the positive side, we present a polynomial time $t$-approximation algorithm for WEIGHTED MAXIMUM CLIQUE on $t$-interval graphs, improving earlier work with approximation ratio $4t$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Toroidal maps : Schnyder woods, orthogonal surfaces and straight-line representations

A Schnyder wood is an orientation and coloring of the edges of a planar map satisfying a simple local property. We propose a generalization of Schnyder woods to graphs embedded on the torus with application to graph drawing. We prove several properties on this new object. Among all we prove that a graph embedded on the torus admits such a Schnyder wood if and only if it is an essentially 3-connected toroidal map. We show that these Schnyder woods can be used to embed the universal cover of an essentially 3-connected toroidal map on an infinite and periodic orthogonal surface. Finally we use this embedding to obtain a straight-line flat torus representation of any toroidal map in a polynomial size grid.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

C*-algebras Associated do Stationary Ordered Bratteli Diagrams

In this paper, we introduce a C*-algebra associated to any substitution (via its Bratteli diagram model). We show that this C*-algebra contains the partial crossed product C*-algebra of the corresponding Bratteli-Vershik system and show that these algebras are invariant under equivalence of the Bratteli diagrams. We also show that the isomorphism class of the algebras, together with a distinguished set of generators, is a complete invariant for equivalence of Bratteli diagrams.

0 citations0 reviewsNo code linkedOpen access