  Graph-based methods, which decompose the score of a dependency tree into
scores of dependency arcs, are popular in dependency parsing for decades.
Recently, \citet{Yang2022Span} propose a headed-span-based method that
decomposes the score of a dependency tree into scores of headed spans. They
show improvement over first-order graph-based methods. However, their method
does not score dependency arcs at all, and dependency arcs are implicitly
induced by their cubic-time algorithm, which is possibly sub-optimal since
modeling dependency arcs is intuitively useful. In this work, we aim to combine
graph-based and headed-span-based methods, incorporating both arc scores and
headed span scores into our model. First, we show a direct way to combine with
$O(n^4)$ parsing complexity. To decrease complexity, inspired by the classical
head-splitting trick, we show two $O(n^3)$ dynamic programming algorithms to
combine first- and second-order graph-based and headed-span-based methods. Our
experiments on PTB, CTB, and UD show that combining first-order graph-based and
headed-span-based methods is effective. We also confirm the effectiveness of
second-order graph-based parsing in the deep learning age, however, we observe
marginal or no improvement when combining second-order graph-based and
headed-span-based methods. Our code is publicly available at
\url{https://github.com/sustcsonglin/span-based-dependency-parsing}.
