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

Dror Rawitz

Dror Rawitz contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and AlgorithmsDiscrete MathematicsComputational Geometrymath.CO

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
4topics
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

4 published item(s)

preprint2026arXiv

Degree Realization by Bipartite Multigraphs

The problem of realizing a given degree sequence by a multigraph can be thought of as a relaxation of the classical degree realization problem (where the realizing graph is simple). This paper concerns the case where the realizing multigraph is required to be bipartite. The problem of characterizing sequences that can be realized by a bipartite graph has two variants. In the simpler one, termed BDR$^P$, the partition of the sequence into two sides is given as part of the input. A complete characterization for realizability in this variant was given by Gale and Ryser over sixty years ago. However, the variant where the partition is not given, termed BDR, is still open. For bipartite multigraph realizations, there are also two variants. For BDR$^P$, where the partition is given as part of the input, a characterization was known for determining whether there is a multigraph realization whose underlying graph is bipartite, such that the maximum number of copies of an edge is at most $r$. We present a characterization for determining if there is a bipartite multigraph realization such that the total number of excess edges is at most $t$. We show that optimizing these two measures may lead to different realizations, and that optimizing by one measure may increase the other substantially. As for the variant BDR, where the partition is not given, we show that determining whether a given (single) sequence admits a bipartite multigraph realization is NP-hard. Moreover, we show that this hardness result extends to any graph family which is a sub-family of bipartite graphs and a super-family of paths. On the positive side, we provide an algorithm that computes optimal realizations for the case where the number of balanced partitions is polynomial, and present sufficient conditions for the existence of bipartite multigraph realizations that depend only on the largest degree of the sequence.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Efficiently Realizing Interval Sequences

We consider the problem of realizable interval-sequences. An interval sequence comprises of $n$ integer intervals $[a_i,b_i]$ such that $0\leq a_i \leq b_i \leq n-1$, and is said to be graphic/realizable if there exists a graph with degree sequence, say, $D=(d_1,\ldots,d_n)$ satisfying the condition $a_i \leq d_i \leq b_i$, for each $i \in [1,n]$. There is a characterisation (also implying an $O(n)$ verifying algorithm) known for realizability of interval-sequences, which is a generalization of the Erdos-Gallai characterisation for graphic sequences. However, given any realizable interval-sequence, there is no known algorithm for computing a corresponding graphic certificate in $o(n^2)$ time. In this paper, we provide an $O(n \log n)$ time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is non-realizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence, in the same time. Finally, we consider variants of the problem such as computing the most regular graphic sequence, and computing a minimum extension of a length $p$ non-graphic sequence to a graphic one.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Graph Realizations: Maximum and Minimum Degree in Vertex Neighborhoods

The classical problem of degree sequence realizability asks whether or not a given sequence of $n$ positive integers is equal to the degree sequence of some $n$-vertex undirected simple graph. While the realizability problem of degree sequences has been well studied for different classes of graphs, there has been relatively little work concerning the realizability of other types of information profiles, such as the vertex neighborhood profiles. In this paper, we initiate the study of neighborhood degree profiles. We focus on the natural problem of realizing maximum and minimum neighborhood degrees. More specifically, we ask the following question: Given a sequence $D$ of $n$ non-negative integers $0\leq d_1\leq \cdots \leq d_n$, does there exist a simple graph with vertices $v_1,\ldots, v_n$ such that for every $1\le i \le n$, the maximum (resp. minimum) degree in the neighborhood of $v_i$ is exactly $d_i$? We provide in this work various results for both maximum as well as minimum neighborhood degree for general $n$ vertex graphs. Our results are first of its kind that studies extremal neighborhood degree profiles. For maximum neighborhood degree profiles, we provide a {\em complete realizability criteria}. In comparison, we observe that the minimum neighborhood profiles are not so well-behaved, for these our necessary and sufficient conditions for realizability {\em differ by a factor of at most two}.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Minimum Vertex Cover in Rectangle Graphs

We consider the Vertex Cover problem in intersection graphs of axis-parallel rectangles on the plane. We present two algorithms: The first is an EPTAS for non-crossing rectangle families, rectangle families $\calR$ where $R_1 \setminus R_2$ is connected for every pair of rectangles $R_1,R_2 \in \calR$. This algorithm extends to intersection graphs of pseudo-disks. The second algorithm achieves a factor of $(1.5 + \varepsilon)$ in general rectangle families, for any fixed $\varepsilon > 0$, and works also for the weighted variant of the problem. Both algorithms exploit the plane properties of axis-parallel rectangles in a non-trivial way.

0 citations0 reviewsNo code linkedOpen access